1.算法的概念

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

2.算法的特性

1.有窮性

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

2.確定性

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

3.可行性

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

4.輸入

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

5.輸出

一個(gè)算法有一個(gè)或多個(gè)輸出，這些輸出是與輸入有著某種特定關(guān)系的量。

3.好算法的特質(zhì)

1.正確性

算法應(yīng)能夠正確地解決求解問題。

2.可讀性

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

3.健壯性

輸入非法數(shù)據(jù)時(shí)，算法能適當(dāng)?shù)刈龀龇磻?yīng)或進(jìn)行處理，而不會(huì)產(chǎn)生莫名其妙的輸出結(jié)果。

4.高效率與低存儲(chǔ)需求

即算法執(zhí)行省時(shí)、省內(nèi)存：時(shí)間復(fù)雜度低、空間復(fù)雜度低。

4.算法的時(shí)間復(fù)雜度

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

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

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

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

2.復(fù)雜度表示的計(jì)算

1.加法規(guī)則

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

2.乘法規(guī)則

多項(xiàng)相乘，都保留。

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

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

5.算法的空間復(fù)雜度

1.程序的內(nèi)存需求

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

2.例題

3.函數(shù)調(diào)用（遞歸）帶來的內(nèi)存開銷

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