我看了一些關于 O(log n) 時間復雜度的視頻，但后來我在 Internet 教程上嘗試了一些二分搜索方法，現在我更加困惑了。
在計算機科學中，大 O 表示法用于根據演算法的運行時間或空間需求如何隨著輸入大小的增長而增長來對演算法進行分類。
二進制搜索示例： https ://jsfiddle.net/Hoyly/mhynk7gp/3/
function binarySearch(sortedArray, key){
let start = 0;
let end = sortedArray.length - 1;
while (start <= end) {
let middle = Math.floor((start end) / 2);
console.log('count', count,sortedArray[middle]);
if (sortedArray[middle] === key) {
return middle;
} else if (sortedArray[middle] < key) {
start = middle 1;
} else {
end = middle - 1;
}
}
return -1;
}
let count= 0;
console.log('first 1:');
let res1 = binarySearch([1,2,3,4,5,6,7,8],8);
console.log('first 2:');
let res2 = binarySearch([1,2,3,4,5,6,7,8],1);
console.log('answer:',res1,res2);正如您在 jsfiddle 中看到的
如果我嘗試在 8 長度陣列中找到“1”
- 方法呼叫計數為3
- 2^3 = 8
- 這就是人們所說的 O(log n) 函式
但如果我試圖找到“8”
- 呼叫次數為4
- 2^4 != 8
- 從最壞的情況來看，這絕對不是 O(log n) 的定義
uj5u.com熱心網友回復：
時間復雜度是 O(log n )，不是沒有大 O 的 log n。我不會在這里解釋 big-O 的全部含義；請參閱Wikipedia 上的定義。
可以說它只給出了隨著n增長而運行時增長率的上限，并且只有當n足夠大時。即使n = 8 導致 1000 次呼叫，演算法仍然可能是 O(log n )。
uj5u.com熱心網友回復：
這里的二分查找可以多做一個步驟，具體取決于您正在搜索的陣列的哪一半。如果使用它Math.ceil而不是Math.floorthen8將在三個步驟中找到，而1將在四個步驟中找到。
如果我們將其擴展到 128 個專案，那么最后一個專案將在 7 或 8 個步驟中找到（同樣，取決于哪一半）。一般來說，所采取步驟的真正最壞情況是log n 1。但是，對于大 O，我們不考慮常數，只考慮函式的增長率。O(log n 1)簡化為O(log n)。同樣的方式如何O(2n)仍然O(n)。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/424326.html
上一篇：如何解決段樹上的問題
下一篇：將污染減半所需的最少過濾器數量