运行时间 - 部分＃2

这将是部分我约的for循环运行时间运行时间 - 部分＃2

http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L03-BigOhSolutions.htm#PR4包含解决方案的分析问题＃2，我有问题，大约两个特殊的“for”循环

有人可以向我解释如何弄清楚他们两人的跑步时间。谢谢！

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

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

来源

2011-10-10 newprint

第一个片段是O(n^5)。

Top Loop = 0 - O(n) = O(n) iterations 
Middle Loop = 0 - O(n^2) = O(n^2) iterations 
Inner Loop = 0 - O(n^2) = O(n^2) iterations 

Total = O(n^5)

这里的第一个代码段的封闭形式解：（通过数学计算的）

sum = -(1/10)*n + (1/4)*n^2 - (1/4)*n^4 + (1/10)*n^5

这是一个5阶多项式，因此它是：O(n^5)

第二个片段显示为O(n^4)。

Top Loop = 0 - O(n) = O(n) iterations 
Middle Loop = 0 - O(n^2) = O(n^2) iterations 
If statement enters: O(1/n) times 
Inner Loop = 0 - O(n^2) = O(n^2) iterations 

Total = O(n^4)

这里的第二代码段的封闭形式解：（通过数学计算的）

sum = -(1/12)*n + (3/8)*n^2 - (5/12)*n^3 + (1/8)*n^4

这是一个4阶多项式，因此它是：O(n^4)

进一步if语句的效果解释：

中间循环迭代从0到i*i。 if语句检查j是否可以被i整除。但只有当j是i的倍数时才可能。

j多少倍i if 0 <= j < i*i？正是i次。因此中间循环迭代中只有1/i会落入最内圈。

来源

2011-10-10 03:10:19 Mysticial

你能否详细说明一下封闭表格，这就是我最稳定的地方。我正在寻找这样的东西http://stackoverflow.com/questions/7375296/trouble-with-nested-for-loop-running-time – newprint

所以你对我如何设法得到那些封闭形式方程感兴趣？ – Mysticial

for＃1，我想出了这样的东西 Sum（Sum j，j = 0 ..... i * i），i = 0 .......n） – newprint

'N'，以及在第二个for循环语句中的其他变量的关系（...，X < = N， ...）会真正确定它的速度。尝试将一个for循环看成一个racem，第二个语句说明你会做多少圈。例如，变量'n'= 1000，那么你必须运行同一圈1000次，真正浪费时间。希望能让你对事物有更好的看法。

来源

2011-10-10 03:09:22 Nathan

运行时间 - 部分＃2

回答

相关问题