无法找到 Big-Oh 值

Question

请参考下面的代码片段：

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

如果用 Big-Oh Notation 来分析这个片段的运行时间，最合适的值是多少？会是 O(N^4) 吗？

Answer 1

我不得不说

O(n^5)

。我也许错了。

n

是我假设的这个问题中数组的长度。如果你替换它，

i

将在

i < n

时停止，j将在

j < n*n

时停止，

k

将在

k < n * n

时停止。由于它们是嵌套的

for-loops

，因此运行时间是

O(n^5)

Answer 2

我认为是 O(n^5)

我们知道

1 + 2 + 3 + ... + n = n(n+1) / 2 = O(n^2)

1^2 + 2^2 + ... + n^2 = n(n+1)(2n+1) / 6 = O(n^3)

我认为类似的陈述对于更大的幂的总和来说是正确的。

让我们思考一下这两行

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

固定 i 时该循环的时间复杂度为 1 + 2 + ... + (i-1)^2 = (i-1)^2(1 + (i-1)^2) / 2 = O(i^4)

但是在我们的代码中，i 从 0 变为 n-1，所以我们喜欢添加四次方，正如我之前所说的

1^k + 2^k + ... + n^k = O(n^(k+1))

这就是为什么时间复杂度是O(n^5)

Answer 3

给出这段代码，分别考虑每个循环。

sum = 0;
for( i = 0; i < n; i++ )         //L1
    for( j = 0; j < i * i; j++ ) //L2
        for( k = 0; k < j; k++ ) //L3
            sum++;               //

单独考虑最外层循环（L1）。显然这个循环的复杂度是 O(n)。

for( i = 0; i < n; i++ )         //L1
    L2(i);

考虑下一个循环（L2）。这个比较难，但是循环是 O(n^2)。
请参阅此答案，了解为什么循环是 O(n^2)：Big O，你如何计算/近似它？

    for( j = 0; j < i * i; j++ ) //L2
        L3(j);

考虑下一个循环（L3）。既然你知道 L2 循环是 O(N^2)，那么这个循环是什么？ （让读者完成他们的作业）。

        for( k = 0; k < j; k++ ) //L3
            sum++;               //

Answer 4

您需要对数学有一定的了解才能解决这个问题。使用求和技术和公式计算整数之和。我自己也不知道 i^4 的求和公式，但我猜测它是一个多项式，最高阶项是 5 阶，这意味着它是 O(n^5)