为什么此函数/循环为O（log n），而不是O（n）？ [英] Why is this function/loop O(log n) and not O(n)?

问题描述

此函数为O（log（n））。为什么？它不是循环到n吗？

This function is O(log(n)). Why? Isn't it looping up to n?

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

顺便说一句，我对O（n）分析还是很陌生。

I'm pretty new to O(n) analysis by the way. This function sure looks O(n) though since it loops up to n.

推荐答案

此函数肯定是O（n），因为它循环为O（n）：

This loop would be 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））：

But this loop is only O(log(n)):

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

因为 $ i 取值：

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

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

And a sequence that grows in that manner is called "logarithmic".

这篇关于为什么此函数/循环为O（log n），而不是O（n）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！