我們要在網路上找東西的時候，常常會到搜尋引擎裡面，打關鍵字來找文章。然而今天要提到的搜尋演算法，卻和搜尋引擎的「搜尋」兩個字的意思有些不一樣。所謂搜尋演算法，就是一種演算法(之前提到演算法可以看成是一堆步驟，有先後順序，有重覆執行的步驟，有依照條件不同而部分執行的步驟)，這個演算法可以幫忙我們解決一個問題，就是在茫茫大海中找到一根針。
舉例來說，今天可能遇到一個問題，是要找出1到100之間的質數。所謂的質數(prime number)，就是除了1和他本身可以整除以外，其他小於他的數字都沒辦法整除他，舉例來說：7是質數，因為除了1和7，其他數字像是2,3,4,5,6都沒辦法整除7，所以7是質數。也許你會感到奇怪，我們沒事尋找質數要做甚麼呢？其實質數扮演滿多重要的角色，尤其在之前Mr. Friday在〈ClickClickClick的中忍考試 : 民族主義與網路安全?〉提到資訊安全的問題，一些非對稱式的加密演算法，就是建立在質數的基礎上面，因為質數不好分解，所以兩個乘在一起的質數要分解開來，需要花費很多時間，當花費的時間夠久，加密得到的保障也越大，也就達到加密的效果(譬如說某個密件10年後才能公開，這個演算法能夠讓駭客10年內無法解開就算有效)。因此，找到大質數也是件很重要的事情。
然而我們還沒講如何找到這個質數？如果我們要寫成演算法，然後把演算法化成電腦的程式打到電腦裡面，讓電腦幫我們找第1000個質數，我們要怎麼寫呢？首先，我們可以從3開始，然後對每一個數字作下面的步驟：(1) 令 x=2，現在要測試的數字為n，(2) n除以 x，(3) 如果 x 可以整除n，那n就不是質數，把n加1，測試下一個數字是不是質數，(4) 如果x不能整除n，代表n可能是質數，把x加1，重覆 “步驟(2)" 到 “步驟(4)"。(5) 如果 x 加1以後等於n，表示2到n之間的數字都測試過，而且都沒辦法整除n，那麼n就是質數了。
上面這個演算法是基本版演算法，以就是說他可以找出質數來。從這個例子也看到，所謂「搜尋」演算法，就是有一個問題的空間(Problem Space)，在這邊問題空間就是「所有大於2的正整數」。搜尋演算法還有一個「目標」，在這邊就是正整數裡面的「質數」。搜尋演算法有很多種，但相同的就是從「問題空間」裡面找到「目標」。
然而不同的搜尋演算法差別在哪邊呢？有兩個主要的衡量標準：空間複雜度和時間複雜度，其實這個標準只要是演算法都適用。所謂空間複雜度，就是這個演算法所需要的記憶體或是硬碟空間，時間複雜度就是演算法所需要的單位時間。當然有些問題會隨著輸入資料的多寡而有所不同，因此我們設計演算法的人，在分析複雜度(Complexity)的時候，會用時間和輸入資料的大小成哪一種正比的關係來作比較，譬如說如果時間複雜度和輸入資料的一次方成正比，我們就會寫O(n)，代表「近似上」(asymptotically)，如果輸入的資料有100筆，我們就會執行約100個時間單位，O(
)則表示和n的平方成正比關係，如果輸入100筆資料，我們就會執行約10000(也就是100的平方)個時間單位。一個好的演算法，會讓時間的複雜度僅可能達到最小。
)則表示和n的平方成正比關係，如果輸入100筆資料，我們就會執行約10000(也就是100的平方)個時間單位。一個好的演算法，會讓時間的複雜度僅可能達到最小。
因此剛才的質數搜尋演算法，假如我們要找2到100裡面的質數，我們會把2到100裡面每個數字都測試一下，而這個測試一下，其實又花費了一些時間，譬如說測試50這個數字的時候，我們把50和2相除，把50和3相除，一直到把50和49相除，在當中我們發現2可以整除50，25可以整除50等等。因此每個數字都會測試小於他的所有數字(5要測試 2到4 之間的數字，6要測試 2到5 之間的數字，…50要測試 2到49 之間的數字，51要測試 2到50 之間的數字，…99要測試 2到98 之間的數字，100要測試 2到99 之間的數字)，每相除一次算成是一個時間單位，所以剛才的演算法所需要的時間單位，就是O()。
)。
然而我們有改進的空間，譬如說我們測試是否整除50的時候，如果50能夠被2整除，也一定會被25整除，能夠被5整除也一定會被10整除，因為50=2*25=5*10，所以我們對於每一個數字測試一下的時候，只需要測試到
就可以了，像是
約等於7，我們只要測試 2到7 之間的數字是否整除50，因為整除的數字是對稱的(50=2*25=5*10)。這樣子所需要的時間瞬間就少了一半！
就可以了，像是約等於7，我們只要測試 2到7 之間的數字是否整除50，因為整除的數字是對稱的(50=2*25=5*10)。這樣子所需要的時間瞬間就少了一半！
然而近似上來說，這樣子還是需要O()的時間，因此有另外一個方法，就是篩子法(sieve method)，譬如說我們要求2到100之間的質數，我們從2開始，把2的倍數都先刪掉，然後刪掉3的倍數，然後刪掉5的倍數，然後刪掉7的倍數，到最後剩下來的，就是和前面這些數字互質的數字，也都是質數了。至於這個演算法的時間複雜度，也必定比O(n^2)來的快(第一回合刪去2的倍數的時候，數字個數就只剩下原來的一半，接下來要運算的次數當然就越來越少，而之間的方法則是至少有一回合要檢查所有的數字，也就是檢查100是否為質數的時候，需要和2到99之間的數字相除，就已經超過篩子法第一次運算的次數：50次了)！
)的時間，因此有另外一個方法，就是篩子法(sieve method)，譬如說我們要求2到100之間的質數，我們從2開始，把2的倍數都先刪掉，然後刪掉3的倍數，然後刪掉5的倍數，然後刪掉7的倍數，到最後剩下來的，就是和前面這些數字互質的數字，也都是質數了。至於這個演算法的時間複雜度，也必定比O(n^2)來的快(第一回合刪去2的倍數的時候，數字個數就只剩下原來的一半，接下來要運算的次數當然就越來越少，而之間的方法則是至少有一回合要檢查所有的數字，也就是檢查100是否為質數的時候，需要和2到99之間的數字相除，就已經超過篩子法第一次運算的次數：50次了)！
還能再改進嗎？這時候如果我們有數學裡面「數論」(Number Theory)的基礎，我們學過「費馬小定理」，那麼我們就可以設計更快的演算法了！
費馬小定理是說：如果一個數字p是質數，那麼任一整數a的p次方，除以p以後的餘數會等於a。a=2是其中一個情況。這個定理要怎麼用呢？如果我們把2到100之間的數字，都拿來算2的n次方，然後除以這個數字本身，如果餘數是2(因為這邊我們先令a=2來計算，a其實可以是任何數字)，那麼這個數字就是質數了。這樣子2到100裡面每個數字只要測試一個時間單位，尤其2的次方可以用bit-wise運算裡面的left shift來達成(若x=2，x>>5就是2的5次方等於32了)，mod取餘數運算也不難，因此這個演算法有辦法達到O(n)的時間複雜度！(100個數字只要100個單位時間而非100平方的單位時間就可以找完質數)
然而如果我們有注意到的話，其實費馬小定理是說：「如果」p是質數，「則」2的p次方(a先代入2)除以p以後餘數是2，但是卻沒有說：「如果」2的p次方除以p以後餘數是2，「則」p是質數。我們演算法和這個定裡的方向剛好是相反的。因此，我們的演算法用的其實是中國猜測：如果上面的式子成立，則p是質數。費馬小定理則是：如果p是質數，則上面的式子成立。
使用中國猜測的時候，有些數字符合這個等式，卻不是質數，我們叫他為假質數(pseudo-prime)。還好假質數沒有太多，最小的假質數是341，因此這個演算法至少可以先刪掉絕不可能為質數的數字，剩下的再慢慢相除來測試就可以了。
在2002年的時候，印度有間大學(India Institue of Technology)的學生發明了O(n)的檢查質數方法。然而這方法所需要的數學基礎實在不少，連我自己都沒看過，就留給有興趣的讀者自行延伸閱讀了！網頁 Paper
下面附上作者Neeraj Kayal的玉照兩張，以及費馬(Pierre de Fermat)的兩張畫像。
本篇稍微提了一下搜尋演算法，以及搜尋質數為例子，來解釋甚麼是搜尋演算法，以及演算法如何修改來增加效率，讓時間複雜度、空間複雜度降低。其他搜尋演算法包括在一個圖(graph，這邊是抽象化的圖，由一堆點(nodes)和連接點的線(edges)所組成)裡面，尋找「最短路徑」，舉例來說，我們回家可能有很多種走法，但是其中一個走法距離最短，或是時間最快，這也是一種搜尋的題目。下象棋或是其他棋類遊戲，每走一步就會有不同的棋盤出現，因此這種種不同的佈局就是我們的「問題空間」，我們的「目標」就是找到一個佈局，可以讓我們贏得這場比賽。網路中的路由(Routing)，也是另一個例子，怎樣子把網路封包，透過最短的路徑傳出去，或是最快的路徑傳出去，這也是一種搜尋的問題。若還有機會，再回來討論一下搜尋演算法這個題目吧！
參考資料
沒有留言:
張貼留言