i≤n的大O分析我* = 2 vs我< n;我* = 2; [英] Big O Analysis for i <= n; i *= 2 vs i < n; i *= 2;

问题描述

使用>为什么使用此功能的示例/循环O(log n)而不是O(n)?:

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

尽管我可以在for循环中识别出这种通用模式，并且大致了解到该功能是O(log n)，但我想知道为什么在条件i <= n的情况下会出现这种情况.

Although I can recognize this common pattern in the for loop and understand generally that this function is O(log n), I am wondering why this is the case given the condition i <= n.

来自上述链接，来自@paxdiablo的答案:

Taken from the above link from an answer from @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)是有意义的.

It makes sense to me that the function is O(log n) if the loop had the condition i < n.

但是如果条件特别是i <= n，则for (int i = 1; i <= n; i *= 2)我不明白为什么它也是O(log n)，因为:

But if the condition is i <= n specifically, for (int i = 1; i <= n; i *= 2) I don't understand why it is also O(log n) because:

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

推荐答案

实际上，以n=8作为上限的示例，将有四个循环迭代，而不是三个:

In fact, taking an example of n=8 for the upper bound, there would be four iterations of the loop, not three:

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

这可以表示为O(log_2(n) + 1).但是，随着n变得非常大，加号的含义将变得微不足道，而正如@paxdiablo答案所言，我们只剩下O(log_2(n))了.

This can be expressed as O(log_2(n) + 1). However, as n grows very large, the plus one term would become insignificant, leaving us with just O(log_2(n)), as the @paxdiablo answer states.

这篇关于i≤n的大O分析我* = 2 vs我< n;我* = 2;的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！