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

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)。