找出 Big(o)

Question

for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < i*i; j++)
            {
                cout << j << endl;
                result++;
            }
        }

运行这段代码表示 5 总共运行了 30 次。我知道外循环运行 N。尽管内循环给我带来了一些麻烦，因为它不是 n*n 而是 i*i，而且在尝试找出 T(n) 之前我还没有见过这样的循环, 和大 (O).

Answer 1

这个算法是O(n^3)：为了实现这个我们必须弄清楚内码的频率

cout << j << endl;
result++;

被执行。为此，我们需要总结 1*1+2*2+...+n*n = n^3/3+n^2/2+n/6，这是一个众所周知的结果（参见 Sum of the Squares of the First n Natural Numbers）。因此 O(T(n)) = O(1*1+2*2+...+n*n) = O(n^3) 并且算法的（时间）复杂度因此是 O(n^3).

编辑： 如果您想知道为什么这就足够了（另请参阅 Time complexity with examples 中的示例 4），将您的代码重写为单个循环会很有帮助，因此我们可以看到循环添加了恒定数量的指令（对于每个运行的内部代码）：

int i = 0;
int j = 0;

while(i < n) {
    cout << j << endl;
    result++;
    if(j < i * i) j++; //were still in the inner loop
    else {//start the next iteration of the outer loop
        j = 0;
        i++;
    }
}

因此这两个循环 'add' 两个比较加上 if-statement 这只会使条件跳转及其效果更加明确。

找出 Big(o)

Figuring out Big(o)

time

complexity-theory