为什么这个函数/循环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

它没有循环遍历所有元素,在每一步中它跳过上一步的两倍元素 - 因为该$i *= 2部分.也就是说,假设$i从一个大于零的值开始,否则它是一个无限循环:$i将始终0如它所写.

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

这个循环将是O(n):

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

因为$i取值:

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

但是这个循环只有O(log(n)):

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

因为$i取值:

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

以这种方式增长的序列称为"对数".

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),类似于二叉树搜索在每次迭代中将搜索空间减半的方式.