演算法圖解筆記1一二分查詢和大O表示法
閒來無事,翻了翻《演算法圖解》,覺得收穫頗多,所以會陸續整理成筆記,紀錄學習過程。嗯,第一篇先來看看二分查詢和大O表示法吧。
一、二分查詢
二分查詢是一種演算法,其輸入是一個有序的元素列表(必須有序的原因稍後解釋)。如果要查詢的元素包含在列表中,二分查詢返回其位置;否則返回null
。
一般而言,對於包含n
個元素的列表,用二分查詢最多需要log2 n
步,而簡單查詢最多需要n
步。
很多童鞋可能忘了倒數如何計算,這裡我們先複習一下:“對數運算是冪運算的逆運算。”,看看下面的公式,是不是有點回憶起來了。
js實現:
/** * @msg: 二分查詢 * @param {Array} 陣列 * @param {String} 數值 * @return: index */ const binarySearch = (arr, val) => { let start = 0; let end = arr.length - 1; let guess; while (start <= end) { let mid = Math.ceil((start + end) / 2); guess = arr[mid]; if (guess === val) return mid; if (guess > val) { end = mid - 1; } else { start = mid + 1; } } return -1; } binarySearch([1, 3, 5, 7, 9], 3);
一般而言,應選擇效率最高的演算法,以最大限度地減少執行時間或佔用空間。
按照上面的思路,我們使用二分查詢實現了這個函式。嗯,看起來不錯,我們來看看他的執行時間。
線性時間:“最多需要猜測的次數與列表長度相同,這被稱為線性時間 (linear time)。”
例如:“簡單查詢逐個地檢查數字,如果列表包含100個數字,最多需要猜100次。如果列表包含40億個數字,最多需要猜40億次。”
“二分查詢則不同。如果列表包含100個元素,最多要猜7次;如果列表包含40億個數字,最多需猜32次。”
二、大O表示法
“是一種特殊的表示法,指出了演算法的速度有多快。”
“也就是說,隨著元素數量的增加,二分查詢需要的額外時間並不多,而簡單查詢需要的額外時間卻很多。因此,隨著列表的增長,二分查詢的速度比簡單查詢快得多。”
“有鑑於此,僅知道演算法需要多長時間才能執行完畢還不夠,還需知道執行時間如何隨列表增長而增加。這正是大O表示法的用武之地。”
“使用大O表示法,這個執行時間為O (n )。單位秒呢?沒有——大O表示法指的並非以秒為單位的速度。大O表示法讓你能夠比較運算元,它指出了演算法執行時間的增速 。”
“記住,大O表示法計算的是運算元。”
這裡有個問題:
“如果要查詢的是Adit——電話簿中的第一個人,一次就能找到,無需檢視每個條目。考慮到一次就找到了Adit,請問這種演算法的執行時間是O (n )還是O (1)呢?”
“大O表示法說的是最糟的情形。因此,你可以說,在最糟情況下,必須檢視電話簿中的每個條目,對應的執行時間為O (n )。這是一個保證——你知道簡單查詢的執行時間不可能超過O (n )。”