“Blog 的新位置在 http://mmdays.com，本Blog將在 12/22 號之後，不同步更新。還請網友轉往新站留言:)”
Posted By Mr. Thursday
我們要在網路上找東西的時候，常常會到搜尋引擎裡面，打關鍵字來找文章。然而今天要提到的搜尋演算法，卻和搜尋引擎的「搜尋」兩個字的意思有些不一樣。所謂搜尋演算法，就是一種演算法(之前提到演算法可以看成是一堆步驟，有先後順序，有重覆執行的步驟，有依照條件不同而部分執行的步驟)，這個演算法可以幫忙我們解決一個問題，就是在茫茫大海中找到一根針。
舉例來說，今天可能遇到一個問題，是要找出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(
因此剛才的質數搜尋演算法，假如我們要找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，所以我們對於每一個數字測試一下的時候，只需要測試到
然而近似上來說，這樣子還是需要O(
還能再改進嗎？這時候如果我們有數學裡面「數論」(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)，也是另一個例子，怎樣子把網路封包，透過最短的路徑傳出去，或是最快的路徑傳出去，這也是一種搜尋的問題。若還有機會，再回來討論一下搜尋演算法這個題目吧！
參考資料
按我訂閱 MMDays 的文章
用 Email 訂閱 MMDays 
Fermat’s Little Theorem.
Let p be a prime which does not divide the integer a, then a^(p-1) = 1 (mod p).
Corollary.
Let p be a prime and a any integer, then a^p = a (mod p).
質數問題很有趣, 最早是為了解ACM的問題才開始研究的
記得最早看到的paper是同樣的作者寫的”Priime is in P”, 才9頁,
看得一個頭兩個大 XD
不過, 重點是, complexity並不是O(n)
如果是的話, 硬碟所有空間都拿去裝加密結果大概還不夠保護一個密碼吧…
a great book to read –> “Prime Obsession “
[...] http://mmdays.wordpress.com/2007/06/29/search_algorithm_prime_number/ [...]
這篇文章寫的很好，不過我覺得其中有一些地方可以注意一下。
首先，原文一開始所提的是去列出1~n中的所有質數，但是最後講題到的AKS演算法則只是去判斷某個數字是否是質數而已，因此按照原本最簡易的演算法去判斷某個數字是否是質數，也只需要O(n)的時間。
第二，原文中有提到，時間複雜度就是輸入資料的大小和執行時間的關係。而在質數判斷的問題上，輸入的資料為n，假設電腦儲存資料是二進制的，實際上在電腦儲存中只需要O(lg n)位元，因此輸入大小和執行時間是呈現指數關係。
第三，如果是用一進制編碼來討論，就會形成輸入大小和執行時間是多項式關係，不過這在演算法分析上稱為假多項式（pseudo-polynomial），可以在wikipedia上找Pseudo-polynomial time，他舉的例子就是質數分析。
最後，我覺得這篇文章會讓人覺得質數判斷是很容易在多項式時間內解決的問題，不過實際上質數問題是否可在多項式時間內解決，在文中最後所提的AKS演算法出來之前，一直都是一個懸而未解的題目。而AKS演算法的執行時間，可以參考wikipedia上的AKS primality test會比較精確。（因為如果是O(n)，還是指數時間的演算法）
謝謝各位的補充!
之前忘了要用length of n (log(n))來當成計算時間複雜度的基礎
非常謝謝各位的提醒!
——————————-
另外也推薦演算法課本裡面的
Number-Theoretic Algorithms那一章
除了比較詳細的介紹
還介紹了randomized algorithm of primality test:
Miller-Rabin primality test!
——————————-
演算法課本書名是: Cormen, Leiserson, and Rivest. Introduction to Algorithms. The MIT Press.
就是那本厚厚的ItoA啦….:)
[...] 在《從尋找質數談談搜尋演算法》一篇文章裡面提到質數搜尋演算法，約略提到了一點演算法 (Algorithm) 以及 搜尋(search) 演算法。簡單地說，搜尋演算法就是要在一堆可能是答案的輸入資料 (input data) 當中，找出符合條件的答案。之前在《排程問題與CPU Scheduling》裡面提到了Job-Shop Problem是一個很難的排程問題 (Scheduling Problem)，是NP-complete。本篇就簡單介紹一下搜尋演算法、「旅行中的商人」這個問題如何使用搜尋演算法、NP-complete的定義、以及最後提一下對偶問題(Dual Problem)。 [...]