從尋找質數談談搜尋演算法

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($latex n^2$)則表示和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($latex n^2$)。

然而我們有改進的空間,譬如說我們測試是否整除50的時候,如果50能夠被2整除,也一定會被25整除,能夠被5整除也一定會被10整除,因為50=2*25=5*10,所以我們對於每一個數字測試一下的時候,只需要測試到$latex \sqrt{n}$就可以了,像是$latex \sqrt{50}$約等於7,我們只要測試 2到7 之間的數字是否整除50,因為整除的數字是對稱的(50=2*25=5*10)。這樣子所需要的時間瞬間就少了一半

然而近似上來說,這樣子還是需要O($latex n^2$)的時間,因此有另外一個方法,就是篩子法(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),也是另一個例子,怎樣子把網路封包,透過最短的路徑傳出去,或是最快的路徑傳出去,這也是一種搜尋的問題。若還有機會,再回來討論一下搜尋演算法這個題目吧!

參考資料

喜歡這篇文章嗎? 分享出去給作者一點鼓勵吧!