[演算法]二進位搜尋與簡易搜尋

演算法對於網站資料的運算是很重要的,同樣100筆資料,該怎麼尋找,才能最快找出來呢?100次?7次?

此篇文章介紹 二進位搜尋(binary search),以及簡易搜尋來做對照,該用哪種方式呢?

二進位搜尋(binary search)

搜尋方式

將要找的序列數值先從小至大排好(或從大至小),每次搜尋都以中間來找,然候得知高或低,再繼續以同樣方式繼續搜尋。

例如 1 ~ 8 的數字,透過二進位搜尋,最多只需要3次,就能找到要找的數字。假設要找8:

第一次找4,因為每次都要從中間開始找:得知偏低,剩餘 5 ~ 8;

第二次找7:得知偏低,剩餘8;

第三次找8:即找到要找的數值。

最大搜尋次數

二進位搜尋的最大搜尋次數為 log n,(留意底數為2)。

例如:有一個陣列:[1, 3, 5, 7, 9, 11, 13, 15],那麼要找到指定值的最大搜尋次數只要 log 8 = 3 次即可。

最壞的搜尋時間

在最大的搜尋次數時,最差的搜尋時間則是以 O(log n) 來表示。

 

簡易搜尋

搜尋方式

將要找的序列數值先從小至大排好(或從大至小),每次搜尋都以最左邊開始找,然候得知有無找到,若沒找到,再繼續以同樣方式繼續搜尋。

例如 1 ~ 8 的數字,透過簡易搜尋,最多需要8次,才能找到要找的數字。假設要找8:

第一次找1,因為每次都要從最左邊開始找:得知偏低,剩餘 2 ~ 8;

第二次找2:得知偏低,剩餘3 ~ 8;位此類推;

第八次找8:即找到要找的數值。

最大搜尋次數

簡易搜尋的最大搜尋次數為 n

最壞的搜尋時間

在最大的搜尋次數時,最差的搜尋時間則是以 O(n) 來表示。

 

什麼是 大O

大O 符號是一種用來指示演算法速度的特殊符號,顯示出該演算法的快或慢。

假設要找的項目共有n個,透過簡易搜尋的話,最多就是要找 n 次,其執行時間在 大O 符號上就顯示為  O(n),是的,沒有秒數,大O 符號不以秒數指示速度,而是讓使用者比較操作次數,所表達的是演算法的增長速度。

 

搜尋時間依照快至慢,常見的有以下5種

O(log n):二進位搜尋

O(n):簡易搜尋

O(n log n)

O(n的平方)選擇排序

O(n!)

您可在此處留言

搶先留言!

Notify of
avatar
wpDiscuz