1.算法的概念

算法(Algorithm）是對特定問題求解步驟的一種描述，它是指令的有限序列，其中的每條指令表示一個或多個操作。

2.算法的特性

1.有窮性

一個算法必須總在執(zhí)行有窮步之后結束，且每一步都可在有窮時間內完成。
算法必須是有窮的，而程序可以是無窮的

2.確定性

算法中每條指令必須有確切的含義，對于相同的輸入只能得出相同的輸出。

3.可行性

算法中描述的操作都可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)。

4.輸入

一個算法有零個或多個輸入，這些輸入取自于某個特定的對象的集合。

5.輸出

一個算法有一個或多個輸出，這些輸出是與輸入有著某種特定關系的量。

3.好算法的特質

1.正確性

算法應能夠正確地解決求解問題。

2.可讀性

算法應具有良好的可讀性,以幫助人們理解。

3.健壯性

輸入非法數(shù)據(jù)時，算法能適當?shù)刈龀龇磻蜻M行處理，而不會產(chǎn)生莫名其妙的輸出結果。

4.高效率與低存儲需求

即算法執(zhí)行省時、省內存：時間復雜度低、空間復雜度低。

4.算法的時間復雜度

事前預估算法時間開銷T(n)與問題規(guī)模n的關系（T表示“time”)

• 最壞時間復雜度:最壞情況下算法的時間復雜度。
• 平均時間復雜度:所有輸入示例等概率出現(xiàn)的情優(yōu)下，算法的期望運行時間。
• 最好時間復雜度:最好情況下算法的時間復雜度。

1.事后統(tǒng)計的問題

①和機器性能有關，如:超級計算機v.s.單片機
②和編程語言有關，越高級的語言執(zhí)行效率越低
③和編譯程序產(chǎn)生的機器指令質量有關
④有些算法是不能事后再統(tǒng)計的，如:導彈控制算法

2.復雜度表示的計算

1.加法規(guī)則

多項相加，只保留最高階的項，且系數(shù)變?yōu)?。

2.乘法規(guī)則

多項相乘，都保留。

3.常見函數(shù)數(shù)量級比較

①順序執(zhí)行的代碼只會影響常數(shù)項，可以忽略。
②只需挑循環(huán)中的一個基本操作分析它的執(zhí)行次數(shù)與n的關系即可。
③如果有多層嵌套循環(huán),只需關注最深層循環(huán)循環(huán)了幾次。

5.算法的空間復雜度

1.程序的內存需求

①若無論問題規(guī)模怎么變，算法運行所需的內存空間都是固定的常量，
算法空間復雜度為s(n)= o(1)，則稱該算法為原地工作：算法所需的內存空間為常量。
②只需關注存儲空間大小與問題規(guī)模相關的變量。

2.例題

3.函數(shù)調用（遞歸）帶來的內存開銷

一般情況，空間復雜度等于遞歸調用的深度。
注：有的算法各層函數(shù)所需存儲空間不同，分析方法略有區(qū)別。