定義：解決某一問題的求解步驟的描述，在計(jì)算機(jī)中表示為指令的有限序列。
算法的特性：
- 輸入輸出：算法具有零個(gè)或多個(gè)輸入；至少有一個(gè)或多個(gè)輸出
- 有窮性：算法在執(zhí)行有限的步驟后自動(dòng)結(jié)束而不會(huì)出現(xiàn)死循環(huán)
- 確定性：算法的每一步都有確定的含義,不會(huì)出現(xiàn)二義性
- 可行性：算法的每一步都必須是可行的，也就是說每一步都能通過執(zhí)行有限次數(shù)完成。
算法的設(shè)計(jì)要求
- 正確性：算法的正確性是指算法至少應(yīng)該具有輸入、輸出、加工處理的無歧義性、能正確反應(yīng)問題的需求、能夠得到問題的正確答案。
在實(shí)際操作中大致表現(xiàn)為：沒有語法錯(cuò)誤、對(duì)正確的輸入能得出正確的結(jié)果、對(duì)錯(cuò)誤的輸入能給出相應(yīng)的說明、對(duì)于給出的大量測(cè)試數(shù)據(jù)都能得出正確的結(jié)果。 - 可讀性：算法設(shè)計(jì)的另一目的是為了便于閱讀、理解和交流
- 健壯性：當(dāng)輸入數(shù)據(jù)不合法時(shí)，算法也能作出相應(yīng)處理而不是產(chǎn)生異?；蛘叩贸瞿婷畹慕Y(jié)果。
- 時(shí)間效率高和存儲(chǔ)量低：時(shí)間效率即是算法的執(zhí)行時(shí)間；存儲(chǔ)量是指算法執(zhí)行過程中需要的最大存儲(chǔ)空間
算法效率的度量方法
- 事后統(tǒng)計(jì)方法：即通過設(shè)計(jì)好的測(cè)試程序和數(shù)據(jù)，利用計(jì)算機(jī)的計(jì)時(shí)對(duì)不同算法編制的程序的運(yùn)行時(shí)間進(jìn)行比較，從而確定算法效率的高低。
- 事前分析估算方法：在計(jì)算機(jī)程序編制前，依據(jù)統(tǒng)計(jì)方法對(duì)算法進(jìn)行估算。
一個(gè)使用高級(jí)程序語言編寫的程序在計(jì)算機(jī)上的運(yùn)行時(shí)間取決于下列幾個(gè)因素：
1.算法采用的策略、方法
2.編譯產(chǎn)生的代碼質(zhì)量
3.問題的輸入規(guī)模
4.機(jī)器執(zhí)行指令的速度
而我們使用事前分析估算方法時(shí)主要考慮算法采用的策略、方法和問題的輸入規(guī)模
函數(shù)的漸近增長(zhǎng)
- 定義:對(duì)于函數(shù)f(n)與g(n),若存在一個(gè)整數(shù)N,使得對(duì)于任意的n > N;總是f(n) > g(n),那么我們說函數(shù)f(n)的增長(zhǎng)漸近快于g(n)
- 使用場(chǎng)景：使用事前分析估算方法時(shí)可將算法內(nèi)部的執(zhí)行操作的次數(shù)與問題規(guī)模掛鉤形成函數(shù)T(n)，在比較算法的好壞時(shí)，我們可以通過比較不同算法所體現(xiàn)出的函數(shù)T(n)來分辨算法的優(yōu)劣
- 判斷一個(gè)算法的效率時(shí)，函數(shù)中的常數(shù)和其他次要項(xiàng)常常可以忽略，而更應(yīng)該關(guān)注主項(xiàng)（最高階項(xiàng)）的階數(shù)。
- 某個(gè)算法，隨著n（即問題規(guī)模）的增大，它會(huì)越來越優(yōu)于另一算法，或者越來越差于另一算法
