如何计算时间复杂度?

问题描述：

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

I'm really having trouble calculating big O. I get the basics but when it gets to nested for loops and all that, my mind just blanks out. I was asked to write down the complexity of the following algorithm which I have no clue how to do. The input string contains only A,B,C and 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是什么?

答

它是 O(n ^ 2).

DDDDDDDDDDDDDDDDDDDABABABABABABABABABABABAB

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

First n/2 characters are D Last n/2 characters are AB

对于每个AB，(有1/4n个)-O(n)

For each AB, (there are 1/4n such) - O(n)

您正在重设i(从头开始迭代)
移动所有连续元素以填充擦除后创建的间隙.

总计:

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

如何计算时间复杂度?

相关推荐