javascript - 对数复杂度 : Either the book has a typo or what's happening here?

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正如你所说的(第 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 提出修复建议。