Big O Analysis for i <= n; i *= 2 vs i < n; i *= 2;

Question

使用为什么这个函数/循环是O(log n(而不是O(n(的例子？

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

虽然我可以在for循环中识别出这种常见模式，并且大致了解此功能O(log n)，但我想知道为什么在条件i <= n的情况下会这样。

取自上面的链接，来自@paxdiablo的回答：

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

对我来说，如果循环具有条件i < n，则该函数O(log n)是有意义的。

但如果具体i <= n条件，for (int i = 1; i <= n; i *= 2)我不明白为什么它也O(log n)，因为：

1 个

• 输入需要 1 个步骤(log_2 1 ≠ 1(
2 个
• 输入需要 2 个步骤(log_2 2 ≠ 2(
• 3 个输入需要 2 个步骤(log_2 3 ≠ 2(
• 。
• 16 个输入需要 5 个步骤(log_2 16 ≠ 5(

Answer 1

事实上，以上界的n=8为例，循环将有四次迭代，而不是三次：

i=1, i=2, i=4, i=8

这可以表示为O(log_2(n) + 1)。 然而，随着n变得非常大，加一项将变得微不足道，只剩下O(log_2(n))，正如@paxdiablo答案所述。