如何计算时间复杂度？

Question

我真的在计算大 O 时遇到了麻烦。我掌握了基础知识，但是当遇到嵌套 for 循环和所有这些时，我的大脑一片空白。我被要求写下以下算法的复杂性，但我不知道该怎么做。输入字符串仅包含 A、B、C 和 D

string solution(string &S) {
    int length = S.length();
    int i = 0;
    while(i < length - 1)
    {
        if ( (S[i] == 'A' && S[i+1] == 'B') || (S[i] == 'B' && S[i+1] == 'A'))
        {
            S = S.erase(i,2);
            i = 0;
            length = S.length();
        }
        
        if ( (S[i] == 'C' && S[i+1] == 'D') || (S[i] == 'D' && S[i+1] == 'C'))
        {
            S = S.erase(i,2);
            i = 0;
            length = S.length();
        }
        
        i++;
    }
    
    return S;
}

这个算法的大 O 是什么？

Answer 1

它是O(n^2)。

DDDDDDDDDDDDDDDDDDDABABABABABABABABABABABAB

前 n/2 个字符是 D 最后 n/2 个字符是 AB

对于每个 AB，（有 1/4n 个这样的）- O(n)

• 您正在重置 i （从头开始迭代）
• 移动所有连续元素以填充擦除后创建的间隙。

全部的：

O(n)*(O(n) + O(n)) = O(n^2)