爲什麼這個函數/循環O（log n）而不是O（n）？

Question

這個函數是O（log（n））。爲什麼？它不是循環到n嗎？

function fxn($n) { 
    for ($i = 1; $i <= $n; $i *= 2) 
     echo $i; 
} 

我很新的O（n）分析的方式。這個函數確實看起來是O（n），儘管它循環到n。

Answer 1

這個循環將是O（N）：

function fxn($n) { 
    for ($i = 0; $i <= $n; $i++) 
     echo $i; 
} 

因爲$i取值爲：

1, 2, 3, 4, 5, 6, 7, ..., n 

但這種循環只有O（日誌（N））：

function fxn($n) { 
    for ($i = 1; $i <= $n; $i *= 2) 
     echo $i; 
} 

因爲$i取值：

1, 2, 4, 8, 16, 32, 64, ..., n 

以這種方式增長的序列稱爲「對數」。

Answer 2

注：因爲你是從0開始的功能永遠不會結束，並且0 * 2 = 0。我會假設你的循環在1

循環遞增多重啓動每次有2，這就是爲什麼運行時是O(lg(n))。

讓我們考慮一個簡單的例子，其中n = 128

這裏是i的值，對於每一次迭代：1，2，4，8，16，32，64，128。因此，你已經走了通過8個值。

lg(128) = 7 (lg = log in base 2) 
     = 8 - 1 

請注意，- 1是一個常數，所以它不會影響我們的運行時計算。

如果循環增加1（或任何常數k），則運行時間爲O（n）。這裏要考慮的重要事項是幾何系列和算術系列之間的差異，它給您不同的運行時間。

Answer 3

它沒有循環遍歷所有元素，在每一步中它跳過前一步驟的兩倍 - 因爲$i *= 2部分。也就是說，假設$i從大於零的值開始，否則就是無限循環：$i在寫入時總是0。

Answer 4

你的代碼循環達到n，但是而不是通過使它成爲O（n）的那個（或任何常數值）。

這是它做什麼：

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 
     | |  |   |      | 
     +--+-----+-----------+-----------------------+ 
Steps 1 2  3    4 

因爲它的每一次增加一倍，它實際上是爲O（log N），類似的方式二叉樹搜索減半每次迭代的搜索空間。