对数复杂度：这本书有错字还是这里发生了什么？

Question

我现在正在研究算法，我遇到过一个例子，我的回答是 Infinite loop，但在正确的答案中，它说是 O(log2n)。

function someFunc(n) {

    for(var i = 0; i < n; i * 2) { // I think that Infinite loop cannot be O(log2n), can it?
        console.log(i);
    }

}

这里我有点疑惑。我不明白为什么，因为它和下面的Infinite loop一样，不是吗？

function loop(n) {

    while(true) {
        console.log(n)
    }

}

资料来源：Sammie Bae - JavaScript 数据结构和算法 - 2019（第 1 章）

Answer 1

这是书中明显的错误。我发现 a PDF of chapter 1 on the publisher's website 和你说的完全一样 (p.10) :

EXERCISE 5

1   function someFunction(n) {

2

3       for (var i=0;i<n;i*2) {

4           console.log(n);

5       }

6

7   }

（下一页）

Answers
[...]
5. O(log2n) Logarithmic complexity. For a given n, this will operate only log2n times because i is incremented by multiplying by 2 rather than adding 1 as in the other examples.

如评论中所述，此循环实际上永远不会退出。

作者（可能）维护着一个可以找到源代码的 github 存储库，因此您可以提出对 the relevant file

的修复

对数复杂度：这本书有错字还是这里发生了什么？

Logarithmic complexity: Either the book has a typo or what's happening here?

javascript

algorithm

big-o

data-structures