algorithm - 详细的大哦问题

Question

因此，我对作业中的这个问题感到有些困惑。

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

所以我在有点困惑之后得出了这个结论

对于( 1, 2n, n)
对于( 1/3( 1, 3n, 1)
我把它作为 1/3，因为它上升了 3。我只是不确定我是否正确，我们刚刚被介绍到这个所以我有点迷路了。

Answer 1

我不完全确定我理解你在问什么...假设问题是这个嵌套循环的 Big-O 表示法是什么(并假设加法操作是基本操作)

• 外层循环执行了2n次
• 对于外层循环的每次迭代，内层循环执行 n^3/3 次

这意味着内部语句被执行 2n * n^3/3 = (2/3)*n^4。对于大 O 表示法，我们忽略常量，所以这个嵌套循环是 O(n^4)。