为什么这个函数/循环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），类似的方式二叉树搜索减半每次迭代的搜索空间。