我現在正在研究演算法，我遇到過一個例子，我的回答是 anInfinite 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 章）
uj5u.com熱心網友回復：
這是書中明顯的錯誤。我在出版商的網站上找到了第 1 章的 PDF，正如您所說的（第 10 頁）：
練習 5
1 function someFunction(n) { 2 3 for (var i=0;i<n;i*2) { 4 console.log(n); 5 } 6 7 }
（下一頁）
答案
[...]
5. O(log2n) 對數復雜度。對于給定的 n，這只會運行 log2n 次，因為 i 是通過乘以 2 來增加的，而不是像其他示例中那樣加 1。
正如評論中所指出的，這個回圈實際上永遠不會退出。
作者（可能）維護了一個可以找到源代碼的 github 存盤庫，因此您可以對相關檔案提出修復建議
uj5u.com熱心網友回復：
好吧，我想答案很簡單。在第一種情況下，函式有一個停止值。(i < n)，所以如果你作為引數發送 n = 10。當 i 達到那個值時它會停止，不是無限的。
至于第二個函式，while(true) 永遠不會改變，因為它不測驗任何東西。而 true 總是真實的，因此該函式是無限的，至于第一個它有一個停止值。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/355672.html
標籤：javascript 算法 数据结构 大O
下一篇：查找字串串列中的差異