-6

对于以下每个程序片段，给出运行时间的 Big-Oh 分析。我有两个问题，我不是 100% 确定是否正确，有人可以帮助我吗

片段 1：

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

答案：O(n^5) 不确定 n*n??

片段 2：

for(  int  i  =  1;  i  <=  n;  i++ ) 
        for(  int  j  =  1;  j  <=  i  *  i;  j++ )
                             if (j % i == 0)
                   for(  int k  =  0;  k  <  j;  k++)
                  sum++;

答案：O(n^4)

4

2 回答 2

0

分解每个循环的问题空间。从最外层循环开始。真正的循环是什么？

对于第一个问题，我们有以下模式。

  • 外循环将运行n次。
  • 外部内部循环将运行n 2次，并且不受内部循环当前值的约束。
  • 最内层循环最多运行j次，这导致它受外部内层循环的当前值约束。
  • 您的所有步骤都是线性块，这意味着您将以线性方式从 0 到结束条件。

这是总和的实际样子。

线性求和，不跳过或跨过任何东西。

那么，这会转化为什么呢？你必须展开总和。不过，它不会是 O(n 5 )。

对于第二个问题，我们有以下模式。

  • 外部循环最多运行 n 次（包括n次）。
  • 外部内部循环最多运行 i 次（包括i次）。
  • 最里面的循环最多运行j次，条件是j % i == 0. 这意味着不是每次都执行最里面的循环。

我会把这个问题留给你解决。您确实必须采取展开总和并将它们减少为代数对应物的方法。

于 2012-09-29T04:27:28.080 回答
-1

对于片段 1：

 lets say m = n^2
 Sigma(i=0...n)  m Sigma(j=0.....m) j
 => n * (m(m+1)/2)
 => n ^ 5

答案：O(n^5)

对于片段 2：

last loop runs for i-1 times ...
Sigma(i=0...n)  Sigma(j=0.....i-1) Sigma(k=0.....j) k
approximately its Sigma(i=0...n) i^2 
~=> n^3

答案：O(n^3)

于 2012-09-29T04:34:20.297 回答