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

- Justin Copeland

---

有很多好的答案，它们说的[几乎]完全一样;-) - user166390

对不起大家，我觉得用1来初始化$i更有意义 :) - Justin Copeland

这可能与任何想了解 for 循环条件中 < vs <= 有关 https://stackoverflow.com/questions/59557610/big-o-analysis-for-i-n-i-2-vs-i-n-i-2/59557650#59557650 - csguy

Answer 1

它没有循环遍历所有元素，在每一步中，它会跳过前一步元素的两倍 - 因为 $i *= 2 部分。也就是说，假设 $i 的初始值大于零，否则它将是一个无限循环：因为它的写法，$i 总是等于 0。

- Óscar López

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

- paxdiablo

---

离3-4只有2个步骤，离5-8只有3个步骤，等等。正确的。 - csguy

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)。在这里需要考虑的重要事情是等比数列和等差数列之间的差异，这将给出不同的运行时间。

- K Mehta

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

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

- john_science

---

我认为你的第一个示例代码是 O(1)，因为它运行的次数是恒定的。 - fanjavaid

@fanjavaid 第一个函数迭代n次。随着n的增长，循环的迭代次数也增加。如果n是10亿，则循环运行10亿次。这是标准的O(n)操作。 - john_science