<演算法圖鑑>心得筆記-第七章

IgorChien
4 min readSep 12, 2020

--

前言

閱讀學習後紀錄下來,以增加自己的記憶及分享學習心得。

輾轉相除法

求兩數的最大公因數的演算法,也稱「歐幾里德演算法」。

補充:輾轉相除法是一種遞迴算法。只要反覆進行除法,就能求出最大公因數。即使運算的兩個數很大,也能用明確的步驟有效率求出最大公因數。

質數判定法

判定某個自然數是否為「質數」的方法。「質數判定法」在現代加密技術中經常使用的「RSA加密」中,扮演非常重要的角色。「質數」是除了自身和1以外,沒有其它質數因子的自然數。

Sieve Of Eratosthenes
補充:費馬小定理:p=質數,n<p,nᵖmodp=n
能判斷該數為質數的可能性很高的話,可判定該數為「可能質數」。但是在極低的機率下,有存在滿足所有算式的合數。而這樣的合數稱為「卡邁克爾數」或「絕對偽質數」。
實務上多半利用費馬質數判定法等高速的方法。
RSA加密」使用的質數判定方法是改良費馬質數判定法而成的「米勒-拉賓質數判定法」。此方法是經過反覆檢驗後,非質數的機率小於0.5的80次方時,就判定該數為質數。AKS質數判定法」最關鍵的四個重要性
・一般的
・多項式的
・確定性的
・無仰賴的

網頁排名

搜尋網站上用來決定搜尋結果排序的。是一種以網頁之間的超連結個數和品質作為主要因素粗略地分析網頁的重要性的演算法。著名的例子就是「Google」。

Pagerank
補充:以往搜尋網站主要以關鍵字和網頁內文章的關聯性來決定搜尋結果的排序。而此方法沒考慮到網頁內是否包含有用的資訊,使得搜尋結果的精確度不高。而Google搜尋結果的排序,不是只用網頁排名來決定。

河內塔

目的是藉由遊戲來理解「遞迴演算法」(Recursive Algorithm)。

河內塔
補充:遞迴」是指一種通過重複將問題分解為同類的子問題而解決問題的方法。
合併排序」、「快速排序」,都是遞迴演算法的例子。
・遞迴演算法的執行次數:(以上圖河內塔遊戲為例)
n為圓盤數,T(n)為移動次數
解開算式為 T(n)=2ⁿ−1

--

--

IgorChien

Genius is one per cent inspiration, ninety-nine per cent perspiration.學無止盡