0

以下算法的运行时间

int b = 0;
for (i = 0; i < n; i++) 
    for (j = 0; j < i * n; j++)   
        b = b + 5;

我知道第一个循环是O(n)但这就是我所得到的。我认为第二个循环可能是O(n^2)但我越想它就越没有意义。任何指导将不胜感激。

4

4 回答 4

1 
     Statements                                     Iterations
for (i = 0; i < n; i++)           |       n+1
    for (j = 0; j < i * n; j++)   |       0+n+2n+3n...n*n = n*n(n+1)/2
        b = b + 5;                |       n*n(n+1)/2

所以总体而言：O(n 3 )

于 2013-10-03T16:56:55.893 回答
1

我们想将此代码的运行时间表示为 n 的函数。打电话给这个T(n)。

我们可以说，作为和的函数，内循环的运行时间在T(n) = U(0,n) + U(1,n) + ... + U(n-1,n)哪里。U(i,n)in

内部循环将运行i * n时间。U(i,n)只是i * n. _

所以我们明白了T(n) = 0*n + 1*n + 2*n + ... + (n-1)*n = n * (1 + 2 + ... + (n-1))。

的封闭形式(1 + 2 + ... + (n-1))只是(n^2 - n)/2 http://www.wolframalpha.com/input/?i=1+%2B+2+%2B+...+%2B+(n-1)。

所以我们明白了T(n) = n * (1 + 2 + ... + (n-1)) = n * ((n^2 - n)/2) = (n^3 - n^2) / 2，

这是O(n^3)。

于 2013-10-03T16:45:07.227 回答
1 
easiest way would be to use a example

assume n=10 

1st for loop runs 10 times o(n)
2nd loop loop runs 0 if i=0
                   10 time for i=1
                   20 times for i=2
                   30 times for i=3
....  100 times(for i=10) o(n^2)

hope it helps you
于 2013-10-03T16:45:16.027 回答
1

外循环运行n迭代。

当n为0时，内循环执行0*n=0次 当n为1时，内循环执行1*n=n次 当n为2时，内循环执行2*n=2n次 当n为3时，内循环执行3*n=3n次 ... ... 当n为n时，内循环执行n*n=n*n次

所以看起来内部循环总共执行了：

0 + n + 2n + 3n + ... + n*n

将它与外循环相乘n，你得到大约。一种O(n^3)复杂性。

于 2013-10-03T16:46:12.320 回答