分析的for循環

考慮的代碼分析的for循環

int sum = 0; 
for(int i = 1; i <= n*n; i = i*2){ 
    sum++ ; 
}

這個片段如何做一個快速的正確分析它來獲得運行時間最壞情況下的增長級？

如何更改增量語句爲i = i * 3而不是i = i * 2更改最差情況下的運行時間？

，是我們分析的影響，通過改變比較運算符<而不是<=？

來源

2014-09-21 Iartist93

我不明白你的問題...你問問循環在做什麼，以及如果你用i * 3替換i * 2和 Kraal 2014-09-21 18:12:25

可能重複的[大O的純英語解釋]（http://stackoverflow.com/questions/487258/plain-english-explanation-of -big-o） – Whymarrh 2014-09-21 18:16:13

我想得到最壞情況下運行時間的增長順序 – Iartist93 2014-09-21 18:18:38

int sum = 0; 
for(int i = 0; i <= n*n; i = i*2){ 
    sum++ ; 
}

就目前而言，這是一個永不停息的無限循環，因爲i永遠不會改變。由於複雜性僅針對算法定義，算法根據定義應該在有限的時間內終止，因此對於此片段而言未定義。

但是，如果你改變了代碼如下：

int sum = 0; 
for(int i = 1; i <= n*n; i = i*2){ 
    sum++ ; 
}

我們可以用下面分析的複雜性：

讓循環運行k - 1次，並在kth更新用的i終止。因爲它是更好的冗餘，而不是不清楚，這裏是正在發生的事情：

初始化（1） - >試驗（1） - >環路（1）I = 1] - >
更新（2） - >試驗（2） - >環（2）[I = 2] - >
...
更新（K - 1） - >試驗（K - 1） - >環（K - 1 ）[I = 2 ^（K - 2）] - >
更新（K） - >試驗（K） - > STOP [試驗作爲i變爲2 ^（K失敗 - 1）]

在哪裏Update(k)表示kth更新（i = i * 2)。

由於在i增量是否爲使得在pth環路（或等價地，pth updation之後），的i值將是2^(p - 1)，我們可以說，在終止：

2^(k - 1) > (n * n)

在冗長，我們終止了第k次更新。無論i的價值是多少，它會大於(n * n)，或者我們已經爲kth循環消失了。雙方以log base 2：

k ~ 2 * log(n)

這意味着k是O(log(n))。

等效地，循環運行的次數爲O(log(n))。

您可以將這個想法很容易地擴展到任何限制（比如N * N * N）和任何增量（I * 3，我* 4等）

的Big O複雜性將通過使用<代替不受影響<=

來源

2014-09-21 18:16:53 axiom

謝謝@axiom :)知道了..但我不知道是否有方法分析 – Iartist93 2014-09-21 18:42:12

@ larstist93已更新答案。 – axiom 2014-09-22 12:33:00

Actualy這個循環是infinte循環。

i=0 
i=i*2 //0*2=0

所以這個循環永遠不會結束。使i=1獲得2的冪的計數直到n^2不等於。

來源

2014-09-21 18:11:35

這應該是一個評論，而不是一個答案。 – Haris 2014-09-21 18:12:19

難以有人評論與小於50代表 – Damian 2014-09-21 18:12:42

只是指出 – Haris 2014-09-21 18:13:25

-1

任何循環，以analys它。你必須看到2件事。的條件，這將使它的出口，並適用於在條件中使用的變量迭代..

爲您的代碼。你可以注意到，當我從0到n * n（n^2）時，循環停止。而變量i正在像i = i * 2一樣增加。當我以這種方式增加我時，循環會運行log（n^2）次。這可以通過將n^2的示例值（如128）看到，然後逐個手動迭代它。

來源

2014-09-21 18:15:43 Haris

分析的for循環

回答

相關問題