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

您的代码循环最多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)，类似于二叉树搜索在每次迭代中将搜索空间减半的方式。

Answer 3

注意：你的函数永远不会结束，因为你从 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 4

这个循环将是 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

以这种方式增长的序列称为“对数”。