这个双循环的大 O 复杂度

Question

我一直在试图找出这段代码的大 O 复杂性：

void findSection(string s)
{
    string start = "abc";
    string end = "xyz";

    int startIndex = s.find(start);
    string tempS;
    while(startIndex<s.size())
    {
        for(int i=startIndex; i<=s.size()-3; i+=3)
        {
            tempS = s.substr(i,3);
            if(tempS==end)
            {
                return;
            }
        }
        startIndex = s.find(start,startIndex+3);
    }
}

最坏的情况是：

s="abcabcabcabc.......

最初我虽然复杂度是 O(nlog(n))，但在查看这个 link 之后：

我得出的复杂度为：

i=0 ——>   0,3,6,9,…,b   b
i=3 ——>   3,6,9,…,b     b-3
i=6 ——>   6,9,…,b       b-6
i=9 ——>   9,…,b         b-9
i=b ——>                 b-b

b + (b-3) + (b-6) + ... + (b-b) = _____

现在我想它可能是 O(n^2) 但我不确定。感谢您的宝贵时间和帮助。

Answer 1

TDLR：O(N²)

外循环是 N 次迭代（对字符串中的每个字符进行一次迭代）。

内循环：

从外循环的索引开始的正常内循环是N/2。但是因为它增加了 3，所以它是 (N/2)*(1/3)。或者干脆 N/6

N*(N/6) 是 N²/6。因此最高多项式的阶数：N²

Answer 2

Big O 时间复杂度为 O(N*N) 因为您显然正在经历第二个循环，程序仅在迭代 divider 3 次时才结束。准确的说，时间复杂度是 < O(N^2)

这个双循环的大 O 复杂度

Big O Complexity of this double loop

c++

performance

time-complexity