標籤: 暫無標籤

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

1 演算法 -概述

求解問題類的、機械的、統一的方法,它由有限多個步驟組成,對於問題類中的每個給定的具體問題,機械地執行這些步驟就可以得到問題的解答。演算法的這種特性,使得計算不僅可以由人,而且可以由計算機來完成。用計算機解決問題的過程可以分成三個階段:分析問題、設計演算法和實現演算法。

2 演算法 -歷史發展

中國古代的籌算口決與珠算口決及其執行規則就是演算法的雛形,這裡,所解決的問題類是算術運算。古希臘數學家歐幾里得在公元前3世紀就提出了一個演算法,來尋求兩個正整數的最大公約數,這就是有名的歐幾里得演算法,亦稱輾轉相除法。中國早已有「算術「、「演算法」等辭彙,但是它們的含義是指當時的全部數學知識和計算技能,與現代演算法的含義不盡相同。英文algorithm(演算法)一詞也經歷了一個演變過程,最初的拼法為algorism或algoritmi,原意為用阿拉伯數字進行計算的過程。這個詞源於公元 9世紀波斯數字家阿爾·花拉子米的名字的最後一部分。

在古代,計算通常是指數值計算。現代計算已經遠遠地突破了數值計算的範圍,包括大量的非數值計算,例如檢索、表格處理、判斷、決策、形式邏輯演繹等。

在20世紀以前,人們普遍地認為,所有的問題類都是有演算法的。20世紀初,數字家們發現有的問題類是不存在演算法的,遂開始進行能行性研究。在這一研究中,現代演算法的概念逐步明確起來。30年代,數字家們提出了遞歸函數、圖靈機等計算模型,並提出了丘奇-圖靈論題(見可計算性理論),這才有可能把演算法概念形式化。按照丘奇-圖靈論題,任意一個演算法都可以用一個圖靈機來實現,反之,任意一個圖靈機都表示一個演算法。

按照上述理解,演算法是由有限多個步驟組成的,它有下述兩個基本特徵:每個步驟都明確地規定要執行何種操作;每個步驟都可以被人或機器在有限的時間內完成。人們對於演算法還有另一種不同的理解,它要求演算法除了上述兩個基本特徵外,還要具有第三個基本特徵:雖然有些步驟可能被反覆執行多次,但是在執行有限多次之後,就一定能夠得到問題的解答。也就是說,一個處處停機(即對任意輸入都停機)的圖靈機才表示一個演算法,而每個演算法都可以被一個處處停機的圖靈機來實現

3 演算法 -演算法分類

演算法可大致分為基本演算法、數據結構的演算法、數論與代數演算法、計算幾何的演算法、圖論的演算法、動態規劃以及數值分析、加密演算法、排序演算法、檢索演算法、隨機化演算法、并行演算法。
演算法可以宏泛的分為三類:
有限的,確定性演算法 這類演算法在有限的一段時間內終止。他們可能要花很長時間來執行指定的任務,但仍將在一定的時間內終止。這類演算法得出的結果常取決於輸入值。
有限的,非確定演算法 這類演算法在有限的時間內終止。然而,對於一個(或一些)給定的數值,演算法的結果並不是唯一的或確定的。
無限的演算法 是那些由於沒有定義終止定義條件,或定義的條件無法由輸入的數據滿足而不終止運行的演算法。通常,無限演算法的產生是由於未能確定的定義終止條件。

基本演算法:
  1枚舉
  2搜索
       深度優先搜索;廣度優先搜索;啟髮式搜索;遺傳演算法
數據結構的演算法
數論與代數演算法
計算幾何的演算法
圖論的演算法

        哈夫曼編碼;樹的遍歷;最短路徑演算法;最小生成樹演算法;最小樹形圖;網路流演算法;匹配演算法
動態規劃
數值分析
加密演算法
排序演算法
隨機化演算法

4 演算法 -演算法特徵

演算法的五個重要特徵:

1、輸入:一個演算法有零個或多個輸入,以刻畫運算對象的初始情況。例如,在歐幾里得演算法中,有兩個輸入,即m和n。

2、確定性:演算法的每一個步驟必須要確切地定義。即演算法中所有有待執行的動作必須嚴格而不含混地進行規定,不能有歧義性。例如,歐幾里得演算法中,步驟1中明確規定「以m除以n,而不能有類似以m除n以或n除以m這類有兩種可能做法的規定。

3、有窮性:一個演算法在執行有窮步滯后必須結束。也就是說,一個演算法,它所包含的計算步驟是有限的。例如,在歐幾里得演算法中,m和n均為正整數,在步驟1之後,r必小於n,若r不等於0,下一次進行步驟1時,n的值已經減小,而正整數的遞降序列最後必然要終止。因此,無論給定m和n的原始值有多大,步驟1的執行都是有窮次。

4、輸出:演算法有一個或多個的輸出,即與輸入有某個特定關係的量,簡單地說就是演算法的最終結果。例如,在歐幾里得演算法中只有一個輸出,即步驟2中的n。

5、能行性:演算法中有待執行的運算和操作必須是相當基本的,換言之,他們都是能夠精確地進行的,演算法執行者甚至不需要掌握演算法的含義即可根據該演算法的每一步驟要求進行操作,並最終得出正確的結果。

演算法的複雜度

1.時間複雜度:演算法的時間複雜度是指演算法需要消耗的時間資源。

2.空間複雜度:演算法的空間複雜度是指演算法需要消耗的空間資源。其計算和表示方法與時間複雜度類似,一般都用複雜度的漸近性來表示。

5 演算法 -演算法的描述

1、用自然語言描述演算法

前面關於歐幾里得演算法以及演算法實例的描述,使用的都是自然語言。自然語言是人們日常所用的語言,如漢語、英語、德語等。使用這些語言不用專門訓練,所描述的演算法也通俗易懂。

2、用流程圖描述演算法

在數學課程里,我們學習了用程序框圖來描述演算法。在程序框圖中流程圖是描述演算法的常用工具由一些圖形符號來表示演算法。

3、用偽代碼描述演算法

偽代碼是用介於自然語言和計算機語言之間的文字和符號來描述演算法的工具。它不用圖形符號,因此,書寫方便、格式緊湊,易於理解,便於向計算機程序設計語言過度。

6 演算法 -史料記載 

演算法在中國古代文獻中稱為「術」,最早出現在《周髀算經》、《九章算術》。特別是《九章算術》,給出四則運算、最大公約數、最小公倍數、開平方根、開立方根、求素數的埃拉托斯特尼篩法,線性方程組求解的演算法。三國代的劉徽給出求圓周率的演算法:劉徽割圓術。
自唐代以來,歷代更有許多專門論述「演算法」的專著:
唐代:《一位演算法》 一卷,《演算法》 一卷;
宋代:《演算法緒論》 一卷、《演算法秘訣》 一卷;最著名的是楊輝的《楊輝演算法》;
元代:《丁巨演算法》;
明代:程大位 《演算法統宗》
清代:《開平演算法》、《演算法一得》、《演算法全書》。

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

7 演算法 -基本方法

1.遞推法
  遞推法是利用問題本身所具有的一種遞推關係求問題解的一種方法。它把問題分成若干步,找出相鄰幾步的關係,從而達到目的,此方法稱為遞推法。
2.遞歸法
  遞歸指的是一個過程:函數不斷引用自身,直到引用的對象已知
3.窮舉搜索法
  窮舉搜索法是對可能是解的眾多候選解按某種順序進行逐一枚舉和檢驗,並從眾找出那些符合要求的候選解作為問題的解。
4.貪婪法
  貪婪法是一種不追求最優解,只希望得到較為滿意解的方法。貪婪法一般可以快速得到滿意的解,因為它省去了為找最優解要窮盡所有可能而必須耗費的大量時間。貪婪法常以當前情況為基礎作最優選擇,而不考慮各種可能的整體情況,所以貪婪法不要回溯。
5.分治法
  分治法是把一個複雜的問題分成兩個或更多的相同或相似的子問題,再把子問題分成更小的子問題……直到最後子問題可以簡單的直接求解,原問題的解即子問題的解的合併。
6.動態規劃法
  動態規劃是一種在數學和計算機科學中使用的,用於求解包含重疊子問題的最優化問題的方法。其基本思想是,將原問題分解為相似的子問題,在求解的過程中通過子問題的解求出原問題的解。動態規劃的思想是多種演算法的基礎,被廣泛應用於計算機科學和工程領域。
7.迭代法
  迭代法是數值分析中通過從一個初始估計出發尋找一系列近似解來解決問題(一般是解方程或者方程組)的過程,為實現這一過程所使用的方法統稱為迭代法。
8.分支界限法
  與貪婪演算法一樣,這種方法也是用來為組合優化問題設計求解演算法的,所不同的是它在問題的整個可能解空間搜索,所設計出來的演算法雖其時間複雜度比貪婪演算法高,但它的優點是與窮舉法類似,都能保證求出問題的最佳解,而且這種方法不是盲目的窮舉搜索,而是在搜索過程中通過限界,可以中途停止對某些不可能得到最優解的子空間進一步搜索(類似於人工智慧中的剪枝),故它比窮舉法效率更高。

8 演算法 -演算法舉例

求最大公約數:求兩個自然數的最大公約數 

1.設兩個變數M和N

2.如果M < N,則交換M和N

3.M被N除,得到餘數R

4.判斷R=0,正確則N即為「最大公約數」,否則下一步

5.將N賦值給M,將R賦值給N,重做第一步。

上一篇[你死,我活]    下一篇 [北洋園]

相關評論

同義詞:暫無同義詞