代码增长的算法顺序

我在线参加一门课程并坚持以下问题。作为N的函数，以下代码段的最坏情况运行时间的增长顺序是什么？代码增长的算法顺序

int sum = 0; 
for (int i = 1; i <= N*N; i++) 
    for (int j = 1; j <= i; j++) 
     for (int k = 1; k <= j; k++) 
      sum++;

我认为这是N^4顺序的，但似乎这个答案是错的。你能解释一下吗？

来源

2014-03-05 Ankit Kumar

一个试验。

中间循环的一次运行调用的内循环正好为i次，其值为j，在1和i（含）之间。所以它增加sum正好1+2+3+...i次，这是i.(i+1)/2由众所周知的“三角形数字”公式。

外环调用环路中间恰好N^2倍（让我们表示它作为M）中，用的i值1和M（含）之间。所以它增加sum正好1+3+6+...M.(M+1)/2次。同样，这是M.(M+1).(M+2)/6，由不太知名的“四面体数字”公式（http://en.wikipedia.org/wiki/Tetrahedral_number）。

总而言之，中sum终值是N^2.(N^2+1).(N^2+2)/6。

在渐近思维，内环是O(j)，中间的一个O(i^2)（通过求和）和所述外一个O(M^3)（通过求和），即O(N^6)。

另请参阅Faulhaber公式，它显示n^k的总和为O(N^(k+1))（http://en.wikipedia.org/wiki/Faulhaber%27s_formula）。

来源

2014-03-05 09:32:41

让我们表示n = N^2。然后，循环将执行每次k <= i <= j。这将约为n^3/6次。因此，在运行时是O(n^3)= O(N^6)

说明：暂时忽略其中k==i或j==i或j==k，我们把1出6个不同的三元组的情况：

(a1,a2,a3) 
(a1,a3,a2) 
(a2,a1,a3) 
(a2,a3,a1) 
(a3,a2,a1) 
(a3,a1,a2)

总体而言，是n^3三倍。 6个三元组中只有一个服从命令。

来源

2014-03-05 09:06:08

这是为了O(N^6)。您应该注意，并非每个循环都简单地将订单N添加到复杂性中。考虑下面的例子：

int sum = 0; 
for (int i = 1; i <= M; i++) 
    for (int j = 1; j <= i; j++) 
     for (int k = 1; k <= j; k++) 
      sum++;

你应该能够找出它是为了O(M^3)容易，所以如果你更换M=N^2，那么你会得到答案。关键是，在这种情况下，每个内部循环的顺序为O(N^2)，但不是O(N)。

来源

2014-03-05 09:07:51 unsym

最内层的（K）循环的任何给定的运行具有正比于J A的时间，但我们必须做那些对每个j的一个= 1到j =我和那笔1 + 2 + ... +我像i^2一样成长。因此，对于任何给出我我们有一个O（i^2）运行时间，但当然我们必须通过i = N^2来处理i = 1。 i^2对i = 1到N^2的总和为happens to grow like N^6。内循环增值sum正是j倍

来源

2014-03-05 09:23:35

代码增长的算法顺序

回答

相关问题