确定最坏情况算法的时间复杂度

Question

这两种算法是否具有相同的 θ(n^2) θ 特性？

int sum = 0;
for (int i = 0; i < n; i++ )
    for (int j = 0; j < n * n; j++ )
        sum++;

int sum = 0;
for ( int i = 0; i < n; i++)
    for ( int j = 0; j < i; j++)
        sum++;

如果不是，那么这是否意味着该表征不是 θ(n^3)？

int sum = 0;
for ( int i = 0; i < n; i++)
    for ( int j = 0; j < i * i; j++ )
        for ( int k = 0; k < j; k++ )
            sum++;

Answer 1

@Dan，对于第一个，您的意思是 j << n * n 而不是 j n？如果是的话，第一个的时间复杂度就是 θ(n^3)，不是吗？

如果你的意思是 j < n，那么我相信前两个都是 θ(n^2)：第一个需要 n^2 步，第二个需要 1 + 2 + ... + n = n(n+1 )/2 即 θ(n^2)。

我认为第三个是 θ(n^4)，但很难证明。绝对是 O(n^4)。