嗨，这是一个来自考试复习的问题。我必须找到以下代码片段的运行时间（以 Big-O 为单位）。
sum = 0;
for( i = 0; i < n; i++ )
for( j = 0; j < i * i; j++ )
for ( k = 0; k < j; k++ )
++sum;
我认为它是O（n ^ 4）。最里面的循环执行到 n 次，第二个循环执行到 n^2，最外面的循环执行 n 次。谢谢大家的帮助
问问题
249 次
3 回答
3
不，它不是 O(4)。
了解这一点的更好方法是计算循环执行的次数（事实上，这就是代码正在做的事情）。
总和（总和（总和（1，k=0..j），j=0..i*i），i=0..n）
= sum(sum(j,j=0..i*i),i=0..n) = sum(i*i*(i*i+1)/2,i=0..n) 这是在 sum(i^4, i=0..n) 的数量级上，它在 n^5 的数量级上。
本质上是因为中间循环是 i*i 并且正在为每个最里面的循环执行，因此需要计算额外的时间。
在 C++ 中
1 0
2 0
3 6
4 42
5 162
6 462
7 1092
8 2268
9 4284
10 7524
11 12474
12 19734
13 30030
14 44226
15 63336
16 88536
17 121176
18 162792
19 215118
您可以使用此表并计算有限差分（取导数），直到结果为常数或 0。您会发现需要 5 个导数才能得到一个常数列表。这意味着它的列表是 n^5 的顺序。
例如，如果我们有一个列表，其中两个元素之间的每个差异都是一个常数，那么该列表可以用线性函数表示。如果差异的差异是恒定的，那么它将是二次方等（低阶项无关紧要，因为它们被导数/差异转换）
于 2013-03-12T03:10:31.727 回答
1
形式上，使用 Sigma 表示法将有助于以非常精确的方式推断增长顺序。
于 2014-04-14T12:30:54.427 回答
0
你可以简单的想：
In the first loop: i = n
second loop: j = i*i => j = n^2
third loop: k = j => k = n^2
So, the bigO = n * n^2 * n^2 = n^5
于 2014-05-16T03:46:36.453 回答