1.算法的概念
算法(Algorithm）是對(duì)
特定問(wèn)題求解步驟的一種描述，它是指令的有限序列，其中的每條指令表示一個(gè)或多個(gè)操作。
2.算法的特性
1.有窮性
一個(gè)算法必須總在執(zhí)行有窮步之后結(jié)束，且每一步都可在有窮時(shí)間內(nèi)完成。
算法必須是有窮的，而程序可以是無(wú)窮的
2.確定性
算法中每條指令必須有確切的含義，對(duì)于
相同的輸入只能得出相同的輸出。
3.可行性
算法中描述的操作都可以通過(guò)已經(jīng)實(shí)現(xiàn)的
基本運(yùn)算執(zhí)行有限次來(lái)實(shí)現(xiàn)。
4.輸入
一個(gè)算法有
零個(gè)或多個(gè)輸入，這些輸入取自于某個(gè)特定的對(duì)象的集合。
5.輸出
一個(gè)算法有
一個(gè)或多個(gè)輸出，這些輸出是與輸入有著某種特定關(guān)系的量。
3.好算法的特質(zhì)
1.正確性
算法應(yīng)能夠正確地解決求解問(wèn)題。
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í)間開(kāi)銷T(n)與問(wè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ì)的問(wèn)題
①和機(jī)器
性能有關(guān)，如:超級(jí)計(jì)算機(jī)v.s.單片機(jī)
②和編程語(yǔ)言有關(guān)，越高級(jí)的語(yǔ)言執(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.常見(jiàn)函數(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)存需求
①若無(wú)論問(wèn)題規(guī)模怎么變，算法運(yùn)行所需的內(nèi)存空間都是固定的常量，
算法空間復(fù)雜度為s(n)= o(1)，則稱該算法為原地工作：算法所需的內(nèi)存空間為常量。
②只需關(guān)注存儲(chǔ)空間大小與問(wèn)題規(guī)模相關(guān)的變量。
2.例題
文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-736933.html
3.函數(shù)調(diào)用（遞歸）帶來(lái)的內(nèi)存開(kāi)銷
一般情況，空間復(fù)雜度等于遞歸調(diào)用的深度。
注：有的算法各層函數(shù)所需存儲(chǔ)空間不同，分析方法略有區(qū)別。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-736933.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)：算法（特性，時(shí)間復(fù)雜度，空間復(fù)雜度）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
