嵌套循环的大 O 符号计算

Question

for ( int i = 1; i < n*n*n; i *= n ) {
    for ( int j = 0; j < n; j += 2 ) { 
        for ( int k = 1; k < n; k *= 3 ) { 
            cout<<k*n;
        }
    }
}

我在这个练习中遇到了一个问题，我需要找到以下代码的大 O 符号，但我得到了 O(n^5)，其中第一个循环是 n^3，第二个循环 n，第三个循环是 n，我不确定我是否正确。有人可以帮我吗？

Answer 1

你错了。在第一个循环 for ( int i = 1; i < n*n*n; i *= n ) 中注意“语句 3”(i *= n)，在第三个循环 for ( int k = 1; k < n; k *= 3 ) 中也注意“语句 3”(k *= 3)。你对第二个循环的计算很棒。

Answer 2

第一个循环是 i=1 每次乘以 n 直到它的 n^3 所以它的 3 次，这是 O(1)。
第二个循环是 j=1 并且每次添加 2 直到它的 n 所以它的 n/2 次，这是 O(n).
第三个循环是 k=1 并乘以 3 直到它的 n，即 O(log(n))
总体：O(n*log(n))

Answer 3

你的分析不正确。

外层循环每次迭代将i乘以n，从1开始直到n^3。
因此会有 3 次迭代，即 O(1).

中间循环每次迭代将 j 递增 2，从 0 开始直到 n。
因此会有 n/2 次迭代，即 O(n).

内部循环将k乘以3，从1到n。
因此会有log3(n)次迭代，也就是O(log(n)).
如果这一步不清楚，请看这里：Big O confusion: log2(N) vs log3(N).

代码的总时间复杂度是上面所有 3 个表达式的乘积（因为它们是嵌套循环）。
因此是：O(1) * O(n) * O(log(n))，即：O(n*log(n)).

嵌套循环的大 O 符号计算

Big O notation calculation for nested loop

c++

algorithm

time

big-o