算法

算法

算法可以理解為有基本運算及規定的運算順序所構成的完整的解題步驟。或者看成按照要求設計好的有限的確切的計算序列,並且這樣的步驟和序列可以解決一類問題。
  • 中文名稱
    算法
  • 外文名稱
    Algorithm
  • 特    征
    有窮性 確切性 輸入 輸出 可行 
  • 常    用
    計算數據處理和自動推理
  • 學    科
    數學 計算機

基本簡介

​算法可以理解為有基本運算及運算規定的運算順序,所構成的完整的解題步驟。或者看成按照要求設計好的有限的確切的計算序列,並且這樣的步驟和序列可以解決一類問題。

主要特點

算法(Algorithm)是指解題方案的準確而完整的描述,是一系列解決問題的清晰指令,算法代表著用系統的方法描述解決問題的策略機制。也就是說,能夠對一定規範的輸入,在有限時間內獲得所要求的輸出。如果一個算法有缺陷,或不適合於某個問題,執行這個算法將不會解決這個問題。不同的算法可能用不同的時間、空間或效率來完成同樣的任務。一個算法的優劣可以用空間複雜度時間複雜度來衡量。

一個算法應該具有以下七個重要的特徵:

算法可以使用自然語言、偽代碼流程圖等多種不同的方法來描述。

1、有窮性(Finiteness)

算法的有窮性是指算法必須能在執行有限個步驟之後終止

2、確切性(Definiteness)

算法的每一步驟必須有確切的定義;

3、輸入項(Input)

一個算法有0個或多個輸入,以刻畫運算對象的初始情況,所謂0個輸入是指算法本身定出了初始條件;

4、輸出項(Output)

一個算法有一個或多個輸出,以反映對輸入數據加工後的結果。沒有輸出的算法是毫無意義的;

5、可行性(Effectiveness)

算法中執行的任何計算步驟都是可以被分解為基本的可執行的操作步,即每個計算步都可以在有限時間內完成(也稱之為有效性);

6、 高效性(High efficiency)

執行速度快,占用資源少;

7、 健壯性(Robustness)

對數據回響正確。

計算機科學家尼克勞斯-沃思曾著過一本著名的書《數據結構十算法= 程式》,可見算法在計算機科學界與計算機套用界的地位。

基本方法

1.遞推法

遞推算法是一種用若干步可重複的簡運算(規律)來描述複雜問題的方法.

遞推是序列計算機中的一種常用算法。它是按照一定的規律來計算序列中的每個項,通常是通過計算機前面的一些項來得出序列中的指定項的值。其思想是把一個複雜的龐大的計算過程轉化為簡單過程的多次重複,該算法利用了計算機速度快和不知疲倦的機器特點。

2.遞歸法

程式調用自身的編程技巧稱為遞歸( recursion)。 一個過程或函式在其定義或說明中有直接或間接調用自身的一種方法,它通常把一個大型複雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解,遞歸策略只需少量的程式就可描述出解題過程所需要的多次重複計算,大大地減少了程式的代碼量。遞歸的能力在於用有限的語句來定義對象的無限集合。一般來說,遞歸需要有邊界條件、遞歸前進段和遞歸返回段。當邊界條件不滿足時,遞歸前進;當邊界條件滿足時,遞歸返回。 注意: (1) 遞歸就是在過程或函數裡調用自身; (2) 在使用遞歸策略時,必須有一個明確的遞歸結束條件,稱為遞歸出口。

3.窮舉法

窮舉法,或稱為暴力破解法,是一種針對於密碼的破譯方法,即將密碼進行逐個推算直到找出真正的密碼為止。例如一個已知是四位並且全部由數字組成的密碼,其可能共有10000種組合,因此最多嘗試10000次就能找到正確的密碼。理論上利用這種方法可以破解任何一種密碼,問題只在於如何縮短試誤時間。因此有些人運用計算機來增加效率,有些人輔以字典來縮小密碼組合的範圍。

4.貪婪算法

貪婪算法是一種對某些求最優解問題的更簡單、更迅速的設計技術。用貪婪法設計算法的特點是一步一步地進行,常以當前情況為基礎根據某個最佳化測度作最優選擇,而不考慮各種可能的整體情況,它省去了為找最優解要窮盡所有可能而必須耗費的大量時間,它採用自頂向下,以疊代的方法做出相繼的貪心選擇,每做一次貪心選擇就將所求問題簡化為一個規模更小的子問題, 通過每一步貪心選擇,可得到問題的一個最優解,雖然每一步上都要保證能獲得局部最優解,但由此產生的全局解有時不一定是最優的,所以貪婪法不要回溯。 貪婪算法是一種改進了的分級處理方法。其核心是根據題意選取一種量度標準。然後將這多個輸入排成這種量度標準所要求的順序,按這種順序一次輸入一個量。如果這個輸入和當前已構成在這種量度意義下的部分最佳解加在一起不能產生一個可行解,則不把此輸入加到這部分解中。這種能夠得到某種量度意義下最優解的分級處理方法稱為貪婪算法。 對於一個給定的問題,往往可能有好幾種量度標準。初看起來,這些量度標準似乎都是可取的,但實際上,用其中的大多數量度標準作貪婪處理所得到該量度意義下的最優解並不是問題的最優解,而是次優解。因此,選擇能產生問題最優解的最優量度標準是使用貪婪算法的核心。 一般情況下,要選出最優量度標準並不是一件容易的事,但對某問題能選擇出最優量度標準後,用貪婪算法求解則特別有效。最優解可以通過一系列局部最優的選擇即貪婪選擇來達到,根據當前狀態做出在當前看來是最好的選擇,即局部最優解選擇,然後再去解做出這個選擇後產生的相應的子問題。每做一次貪婪選擇就將所求問題簡化為一個規模更小的子問題,最終可得到問題的一個整體最優解。

5.分治法

分治法是把一個複雜的問題分成兩個或更多的相同或相似的子問題,再把子問題分成更小的子問題……直到最後子問題可以簡單的直接求解,原問題的解即子問題的解的合併。

分治法所能解決的問題一般具有以下幾個特徵:

(1) 該問題的規模縮小到一定的程度就可以容易地解決(2) 該問題可以分解為若干個規模較小的相同問題,即該問題具有最優子結構性質。(3) 利用該問題分解出的子問題的解可以合併為該問題的解;(4) 該問題所分解出的各個子問題是相互獨立的,即子問題之間不包含公共的子子問題。

6.動態規劃法

動態規劃是一種在數學和計算機科學中使用的,用於求解包含重疊子問題的最最佳化問題的方法。其基本思想是,將原問題分解為相似的子問題,在求解的過程中通過子問題的解求出原問題的解。動態規劃的思想是多種算法的基礎,被廣泛套用於計算機科學和工程領域。

動態規劃程式設計是對解最最佳化問題的一種途徑、一種方法,而不是一種特殊算法。不象前面所述的那些搜尋或數值計算那樣,具有一個標準的數學表達式和明確清晰的解題方法。動態規劃程式設計往往是針對一種最最佳化問題,由於各種問題的性質不同,確定最優解的條件也互不相同,因而動態規劃的設計方法對不同的問題,有各具特色的解題方法,而不存在一種萬能的動態規划算法,可以解決各類最最佳化問題。因此讀者在學習時,除了要對基本概念和方法正確理解外,必須具體問題具體分析處理,以豐富的想像力去建立模型,用創造性的技巧去求解。

7.疊代法

疊代法也稱輾轉法,是一種不斷用變數的舊值遞推新值的過程,跟疊代法相對應的是直接法(或者稱為一次解法),即一次性解決問題。疊代法又分為精確疊代和近似疊代。“二分法”和“牛頓疊代法”屬於近似疊代法。疊代算法是用計算機解決問題的一種基本方法。它利用計算機運算速度快、適合做重複性操作的特點,讓計算機對一組指令(或一定步驟)進行重複執行,在每次執行這組指令(或這些步驟)時,都從變數的原值推出它的一個新值。

8.分枝界限法

分枝界限法是一個用途十分廣泛的算法,運用這種算法的技巧性很強,不同類型的問題解法也各不相同。分支定界法的基本思想是對有約束條件的最最佳化問題的所有可行解(數目有限)空間進行搜尋。該算法在具體執行時,把全部可行的解空間不斷分割為越來越小的子集(稱為分支),並為每個子集內的解的值計算一個下界或上界(稱為定界)。在每次分支後,對凡是界限超出已知可行解值那些子集不再做進一步分支。這樣,解的許多子集(即搜尋樹上的許多結點)就可以不予考慮了,從而縮小了搜尋範圍。這一過程一直進行到找出可行解為止,該可行解的值不大於任何子集的界限。因此這種算法一般可以求得最優解。 與貪心算法一樣,這種方法也是用來為組合最佳化問題設計求解算法的,所不同的是它在問題的整個可能解空間搜尋,所設計出來的算法雖其時間複雜度比貪婪算法高,但它的優點是與窮舉法類似,都能保證求出問題的最佳解,而且這種方法不是盲目的窮舉搜尋,而是在搜尋過程中通過限界,可以中途停止對某些不可能得到最優解的子空間進一步搜尋(類似於人工智慧中的剪枝),故它比窮舉法效率更高。

基本術語

算法分類

算法可大致分為基本算法、數據結構的算法、數論與代數算法、計算幾何的算法、圖論的算法、動態規劃以及數值分析、加密算法、排序算法、檢索算法、隨機化算法、並行算法,厄米變形模型,隨機森林算法。。

算法可以宏泛的分為三類:

有限的,確定性算法 這類算法在有限的一段時間內終止。他們可能要花很長時間來執行指定的任務,但仍將在一定的時間內終止。這類算法得出的結果常取決於輸入值。

有限的,非確定算法 這類算法在有限的時間內終止。然而,對於一個(或一些)給定的數值,算法的結果並不是唯一的或確定的。

無限的算法 是那些由於沒有定義終止定義條件,或定義的條件無法由輸入的數據滿足而不終止運行的算法。通常,無限算法的產生是由於未能確定的定義終止條件。

算法的表示形式

描述算法的方法有多種,常用的有自然語言、結構化流程圖、偽代碼和PAD圖等,其中最普遍的是流程圖。

算法

其他資料

算法的評價

同一問題可用不同算法解決,而一個算法的質量優劣將影響到算法乃至程式的效率。算法分析的目的在於選擇合適算法和改進算法。一個算法的評價主要從時間複雜度空間複雜度來考慮。

1.時間複雜度

算法的時間複雜度是指執行算法所需要的時間。一般來說,計算機算法是問題規模n 的函式f(n),算法的時間複雜度也因此記做

T(n)=Ο(f(n))

因此,問題的規模n 越大,算法執行的時間的增長率與f(n) 的增長率正相關,稱作漸進時間複雜度(Asymptotic Time Complexity)。

2.空間複雜度

算法的空間複雜度是指算法需要消耗的記憶體空間。其計算和表示方法與時間複雜度類似,一般都用複雜度的漸近性來表示。同時間複雜度相比,空間複雜度的分析要簡單得多。

詳見百度百科詞條"算法複雜度"

套用舉例

經典的算法有很多,如:"歐幾里德算法,割圓術,秦九韶算法 ,輾轉相除法"。隨著計算機的發展,算法在計算機方面已有廣泛的發展及套用,如用隨機森林算法,來進行頭部姿勢的估計,用遺傳算算法來解決彈藥裝載問題,信息加密算法在網路傳輸中的套用,並行算法在數據挖掘中的套用等。

算法經典專著

目前市面上有許多論述算法的書籍,其中最著名的便是《電腦程式設計藝術》(The Art Of Computer Programming) 以及《算法導論》(Introduction To Algorithms)。

算法的歷史

“算法”即演算法的大陸中文名稱出自《周髀算經》;而英文名稱Algorithm 來自於9世紀波斯數學家al-Khwarizmi,因為al-Khwarizmi在數學上提出了算法這個概念。“算法”原為"algorism",意思是阿拉伯數字的運算法則,在18世紀演變為"algorithm"。歐幾里得算法被人們認為是史上第一個算法。 第一次編寫程式是Ada Byron於1842年為巴貝奇分析機編寫求解解伯努利方程的程式,因此Ada Byron被大多數人認為是世界上第一位程式設計師。因為查爾斯·巴貝奇(Charles Babbage)未能完成他的巴貝奇分析機,這個算法未能在巴貝奇分析機上執行。 因為"well-defined procedure"缺少數學上精確的定義,19世紀和20世紀早期的數學家、邏輯學家在定義算法上出現了困難。20世紀的英國數學家圖靈提出了著名的圖靈論題,並提出一種假想的計算機的抽象模型,這個模型被稱為圖靈機。圖靈機的出現解決了算法定義的難題,圖靈的思想對算法的發展起到了重要作用的。

求素數的埃拉托塞尼篩法和求方根的開方的方法公式(算法不等於公式,公式卻是提供一種算法)

典型算法舉例:

歷史上有三大算法:

1,求最大公約數的歐幾里得輾轉相除法;

2,求素數的埃拉托塞尼篩法;

3,求方根的開方算法。後面兩種方法都可以用公式表達。

一,求素數的埃拉托塞尼篩法公式

。屬於遞歸的。

算法與公式的關係:

公元前250年同樣是古希臘的數學家埃拉托塞尼提出一種篩法:

(一)“要得到不大於某個自然數N的所有素數,只要在2---N中將不大於√N的素數的倍數全部划去即可”。

(二)將上面的內容等價轉換:“如果N是合數,則它有一個因子d滿足1<d≤√N”。(《基礎數論》13頁,U杜德利著,上海科技出版社)。.

(三)再將(二)的內容等價轉換:“若自然數N不能被不大於(根號)√N的任何素數整除,則N是一個素數”。見(代數學辭典[上海教育出版社]1985年。屜部貞世朗編。259頁)。

(四)這句話的漢字可以等價轉換成為用英文字母表達的公式:

N=p1m1+a1=p2m2+a2=......=pkmk+ak 。(1)

其中 p1,p2,.....,pk表示順序素數2,3,5,,,,,。a≠0。即N不能是2m+0,3m+0,5m+0,...,pkm+0形。若N<P(k+1)的平方 [註:後面的1,2,3,....,k,(k+1)是腳標,由於列印不出來,凡字母后面的數字或者i與k都是腳標] ,則N是一個素數。

(五)可以把(1)等價轉換成為用同餘式組表示:

N≡a1(modp1), N≡a2(modp2),.....,N≡ak(modpk)。 (2)

例如,29,29不能夠被根號29以下的任何素數2,3,5整除,29=2x14+1=3x9+2=5x5+4。 29≡1(mod2),29≡2(mod3), 29≡4(mod5)。29小於7的平方49,所以29是一個素數。

以後平方用“*”表示,即:㎡=m*。

由於(2)的模p1,p2,....,pk 兩兩互素,根據孫子定理(中國剩餘定理)知,(2)在p1p2.....pk範圍內有唯一解。

例如k=1時,N=2m+1,解得N=3,5,7。求得了(3,3*)區間的全部素數。

k=2時,N=2m+1=3m+1,解得N=7,13,19; N=2m+1=3m+2,解得N=5,11,17,23。求得了(5,5*)區間的全部素數。

k=3時,

---------------------| 5m+1-|- 5m+2-| 5m+3,| 5m+4.|

---------------------|---------|----------|--------|---------|

n=2m+1=3m+1= |--31----|--7, 37-|-13,43|--19----|

n=2m+1=3m+2= |-11,41-|-17,47-|--23---|---29---|

------------------------------------------------------------

求得了(7,7*)區間的全部素數。

仿此下去,可以求得任意大的數以內的全部素數。

二,求方根的開方方法公式;

開方的反饋方法或者叫做自動調節開方。方法是疊代的。

公式:

X_(n+1)={X_n+【A/(X^(k-1))-X_n】1/k}

"_"表示下角標,“^”表示上角標。例如,X^2,表示x的平方;X_1表示第一個X。

例如,A=5,k=3.即開3次方。

公式:X(n+1)=Xn+(A/Xn^2-Xn)1/3

5介於1^3至2^3之間(1的3次方=1,2的3次方=8)

X_0可以取1.1,1.2,1.3,1.4,1.5,1.6,1.7,1.8,1.9,2.0都可以。例如我們取2.0.按照公式:

第一步:X_1={2.0+[5/(2.0^2)-2.0]1/3=1.7.}。即5/2×2=1.25,1.25-2=-0.75,0.75×1/3=0.25,

2-0.25=1.75,取2位數值,即1.7。

第二步:X_2={1.7+[5/(1.7^2)-1.7]1/3=1.71}.。即5/1.7×1.7=1.73010,1.73-1.7=0.03,0.03×1/3=0.01,

1.7+0.01=1.71。取3位數,比前面多取一位數。

第三步:X_3={1.71+[5/(1.71^2)-1.71]1/3=1.709}

第四步:X_4={1.709+[5/(1.709^2)-1.709]1/3=1.7099}.

這種方法可以自動調節,第一步與第三步取值偏大,但是計算出來以後輸出值會自動轉小;第二步,第四步輸入值偏小,輸出值自動轉大。X_4=1.7099.

當然也可以取1.1,1.2,1.3,。。。1.8,1.9中的任何一個。

開平方公式

X(n + 1) = Xn + (A / Xn ? Xn)1 / 2.。(n,n+1與是下角標)

例如,A=5:

5介於2的平方至3的平方;之間。我們取初始值2.1,2.2,2.3,2.4,2.5,2.6,2.7,2.8,2.9都可以,我們最好取 中間值2.5。

第一步:2.5+(5/2.5-2.5)1/2=2.2;

即5/2.5=2,2-2.5=-0.5,-0.5×1/2=-0.25,2.5+(-0.25)=2.25,取2位數2.2。

第二步:2.2+(5/2.2-2.2)1/2=2.23;

即5/2.2=2.27272,2.27272-2.2=-0.07272,-0.07272×1/2=-0.03636,2.2+0.03636=2.23。取3位數2.23。

第三步:2.23+(5/2.23-2.23)1/2=2.236。

即5/2.23=2.2421525,,2.2421525-2.23=0.0121525,,0.0121525×1/2=0.00607,,2.23+0.006=2.236.,取4位數。

每一步多取一位數。這個方法又叫反饋開方,即使你輸入一個錯誤的數值,也沒有關係,輸出值會自動調節,接近準確值。

例如A=200.

200介如10的平方---20的平方之間。初始值可以取11,12,13,14,15,16,17,18,19。我們去15.

15+(200/15-15)1/2=14。取19也一樣得出14.。:19+(200/19-19)1/2=14.。

14+(200/14-14)1/2=14.1。

14.1+(200/14.1-14.1)1/2=14.14.

中間值,即1.5。 1.5+(5/1.5^2;-1.5)1/3=1.7。

順便介紹開5次方公式:

X(n+1)=Xn+(A/X^4-Xn)1/5 . (n,n+1是下角標)

例如:A=5;

5介入1的5次方至2的5次方之間。2的5次方是32,5靠近1的5次方。初始值可以取1.1,1.2,1.3,1.4,1.5,1.6,1.7,1.8,1.9.例如我們取中間值1.4;

1.4+(5/1.4^4-1.4)1/5=1.38

1.38+(5/1.38^4-1.38)1/5=1.379.

1.379+(5/1.379^4-1.379)1/5=1.3797.

計算次數與精確度成為正比。即5=1.3797^5。    

相關

經典的算法有很多,如歐幾里德算法割圓術秦九韶算法

隨著計算機的發展,算法在計算機方面已有廣泛的發展及套用,如用隨機森林算法,來進行頭部姿勢的估計,用遺傳算法來解決彈藥裝載問題,信息加密算法在網路傳輸中的套用,並行算法在數據挖掘中的套用等。

數量地理學

▪數量地理學▪計算地理學▪數理地理學▪地學統計▪地學計算
▪算法▪計量革命▪人地關係動力學▪環境動力學▪區域動力學
▪孤立系統▪封閉系統▪地理控制論▪地理系統工程▪地理系統分析
▪動態系統▪控制系統▪宏系統▪巨系統▪複雜系統
▪混雜系統▪分散式系統▪遞階系統▪格線系統▪狀態空間
▪複雜性▪不確定性▪風險▪自主體▪均衡
▪平衡▪平衡點▪極限環▪穩態▪分叉





相關詞條

相關搜尋