运行时间的算法

Question

嗨，这是一个考试复习的问题。我必须找到以下代码片段的运行时间（在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次。谢谢大家的帮助

Answer 1

不，它不是O（4）。

更好的方法来看这是计算循环执行多少次（实际上，这就是代码的工作）。

总和（求和（总和（1，K = 0..j）中，j = 0..i * I）中，i = 0到n）

=总和（总和（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++

http://codepad.org/nKJ9IUnt

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。

例如，如果我们有一个列表，其中两个元素之间的每个差异是常量，那么列表可以用线性函数表示。如果差异的差异是恒定的，那么它将是一个四极等等（它对于较低阶项而言并不重要，因为它们被导数/差值翻译）

Answer 2

形式上，使用Sigma符号将有助于精确地推导增长的顺序。

Answer 3

你可以简单地认为：在最里面的循环

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