什么是算法分析
當(dāng)我們說(shuō)算法分析的時(shí)候我們?cè)谡f(shuō)什么义矛？（狹義的技術(shù)層面的定義）：
算法分析指的是：對(duì)算法在運(yùn)行時(shí)間和存儲(chǔ)空間這兩種資源的利用效率進(jìn)行研究妨托。
即時(shí)間效率和空間效率缸榛。
時(shí)間效率指算法運(yùn)行有多快；
空間效率指算法運(yùn)行時(shí)需要多少額外的存儲(chǔ)空間兰伤。
（時(shí)間效率也叫時(shí)間復(fù)雜度内颗；空間效率也叫空間復(fù)雜度。）
在計(jì)算機(jī)時(shí)代早期敦腔，時(shí)間和空間這兩種資源都是及其昂貴的均澳。但經(jīng)過(guò)半個(gè)多世紀(jì)的發(fā)展，計(jì)算機(jī)的速度和存儲(chǔ)容量都已經(jīng)提升了好幾個(gè)數(shù)量級(jí)符衔。
現(xiàn)在空間效率已經(jīng)不是我們關(guān)注的重點(diǎn)了找前，但時(shí)間效率的重要性并沒(méi)有減弱到這種可以忽略的程度。
所以柏腻，當(dāng)我們分析一個(gè)算法的的時(shí)候纸厉，我們只關(guān)注它的時(shí)間效率。
算法分析通用思路：
當(dāng)我們遇到一個(gè)算法時(shí)五嫂，我們可以用這樣一個(gè)通用的思路去分析它：
1. 輸入規(guī)模
首先第一步考慮這個(gè)算法的輸入規(guī)模是什么颗品？即輸入?yún)?shù)，再換句話說(shuō)也就是待解決的問(wèn)題有多大沃缘？
從這里入手是因?yàn)橐粋€(gè)顯而易見(jiàn)的規(guī)律就是躯枢，不管使用什么算法，輸入規(guī)模越大槐臀，運(yùn)行效率肯定會(huì)更長(zhǎng)锄蹂。
輸入規(guī)模的確定要根據(jù)具體要解決的實(shí)際問(wèn)題的細(xì)節(jié)來(lái)決定，相同的問(wèn)題不同的細(xì)節(jié)水慨，輸入規(guī)模是不一樣的得糜。比如：一個(gè)拼寫檢查的算法，
如果算法關(guān)注的是單獨(dú)的字符檢查晰洒，那么字符的數(shù)量就是輸入規(guī)模的大谐丁；
如果算法關(guān)注的是詞組搭配的檢查谍珊，那么這個(gè)輸入規(guī)模就要比單獨(dú)的字符檢查的輸入規(guī)模要小治宣，這里輸入規(guī)模就是詞的數(shù)量了。
2. 運(yùn)行時(shí)間的度量單位
接下來(lái)第二步考慮這個(gè)算法的運(yùn)行時(shí)間，即這個(gè)算法運(yùn)行地快慢侮邀。
我們可以簡(jiǎn)單地用計(jì)時(shí)的方法坏怪，即某個(gè)算法運(yùn)行了多少毫秒。
但這個(gè)方式有一個(gè)缺陷就是在不同計(jì)算機(jī)上绊茧，相同算法的運(yùn)行時(shí)間是不一樣铝宵，因?yàn)橛械碾娔X快有的電腦慢。
所以有沒(méi)有一種度量方法可以排除這些無(wú)關(guān)因素按傅？
答案是肯定的捉超，我們可以關(guān)注算法執(zhí)行了多少步，即操作的運(yùn)行次數(shù)唯绍。而且為了簡(jiǎn)化問(wèn)題我們只需關(guān)注最重要的操作步驟，即所謂的基本操作枝誊，因?yàn)榛静僮饕呀?jīng)足夠可以決定這個(gè)算法的品質(zhì)况芒。
比如一個(gè)算法通常是最內(nèi)層的循環(huán)中是最費(fèi)時(shí)的操作，那我們就只需要把它循環(huán)了多少次作為基本操作進(jìn)行研究叶撒。
3. 增長(zhǎng)次數(shù)
這里需要延伸的一點(diǎn)是在大規(guī)模的輸入情況下考慮執(zhí)行次數(shù)的增長(zhǎng)次數(shù)绝骚。因?yàn)獒槍?duì)小規(guī)模的輸入，在運(yùn)行時(shí)間的差別上不太明顯祠够。比如只對(duì)100個(gè)數(shù)字進(jìn)行排序压汪，不管你用什么排序算法，時(shí)間效率都差不多古瓤。只有在輸入規(guī)模變大的時(shí)候止剖，算法的差異才變得既明顯又重要了起來(lái)。
簡(jiǎn)單來(lái)說(shuō)落君，
如果一個(gè)算法在輸入規(guī)模變大時(shí)穿香，但運(yùn)行時(shí)間平緩增長(zhǎng)，那么我們就可以說(shuō)它就是一個(gè)效率高的算法绎速；
而如果一個(gè)算法在輸入規(guī)模變大時(shí)皮获，它的運(yùn)行時(shí)間成指數(shù)級(jí)增長(zhǎng)，那就可以說(shuō)這個(gè)算法的效率很差纹冤。
總而言之就是洒宝，對(duì)基本操作的大規(guī)模輸入情況下的變化的研究才更具有深遠(yuǎn)意義。
4. 算法的最優(yōu)萌京、最差和平均效率
當(dāng)我們了解了輸入規(guī)模對(duì)算法時(shí)間效率的會(huì)產(chǎn)生影響雁歌，但算法的執(zhí)行效率卻不僅僅只受輸入規(guī)模的影響，某些情況下枫夺，算法的執(zhí)行效率更取決于輸入?yún)?shù)的細(xì)節(jié)将宪。
比如：一個(gè)簡(jiǎn)單的順序查找的算法，在數(shù)組里查找數(shù)字 9：
在數(shù)組 l1 = [1, 2, 3, 4, 5, 6, 7, 8, 9] 里查找數(shù)字 9 和在相同的輸入規(guī)模的另一個(gè)數(shù)組 l2 = [9, 1, 2, 3, 4, 5, 6, 7, 8]里查找數(shù)字 9，在數(shù)組 l2 的執(zhí)行效率肯定更高较坛。
上面小例子中的兩個(gè)數(shù)組就體現(xiàn)了兩個(gè)極端：輸入最優(yōu)情況和輸入最壞情況印蔗。
相對(duì)應(yīng)的，
在輸入最優(yōu)情況下的算法就叫最優(yōu)效率丑勤；
在輸入最壞情況下的算法就叫最差效率华嘹；
在這里有兩個(gè)經(jīng)驗(yàn)性的規(guī)則：
- 最優(yōu)效率的分析遠(yuǎn)遠(yuǎn)不如最差效率分析重要（因?yàn)樽畈钚士梢源_定算法運(yùn)行時(shí)間的上界）；
- 如果一個(gè)算法的最優(yōu)效率都不能滿足我們的要求法竞，那么我們就可以立即拋棄它耙厚。
在現(xiàn)實(shí)情況下，輸入是“隨機(jī)”的岔霸，既不會(huì)是最優(yōu)輸入也不會(huì)是最壞輸入薛躬。所以這里又要引出一個(gè)概念，即：平均效率呆细。
首先指出型宝，我們絕不能用“最優(yōu)效率”和“最差效率”的平均數(shù)求得平均效率，即便有時(shí)間這個(gè)平均數(shù)和真正的平均效率巧合地一致絮爷。
正確的步驟是：我們要對(duì)輸入規(guī)模 n 做一些假設(shè)趴酣。
對(duì)于上面的順序查找算法的例子，標(biāo)準(zhǔn)的假設(shè)有兩個(gè)：
- 輸入里包含目標(biāo)數(shù)字坑夯，那么算法會(huì)成功查找到目標(biāo)數(shù)字岖寞，此時(shí)，成功查找概率是 p(0 <= p <= 1)柜蜈；
- 對(duì)于任意數(shù)字 i仗谆，匹配發(fā)生在列表的第 i 個(gè)位置的概率是相同的。
基于這兩個(gè)假設(shè)求平均效率可得：
- 成功查找到目標(biāo)的情況下跨释，對(duì)于任意 i胸私，第一次匹配發(fā)生在第 i 個(gè)位置的概率都是 p/n，此時(shí)鳖谈，算法所做的比較次數(shù)是 i岁疼；
- 輸入數(shù)組里不包含目標(biāo)數(shù)字，那么算法不成功查找缆娃，比較次數(shù)是 n捷绒，在這種情況下，可能性是 (1-p)贯要。
由此暖侨，平均效率 C(n) = p(n+1) / 2 + n(1-p)
C(n) = [1 * p/n + 2 * p/n + ... + i * p/n + ... + n * p/n] + n*(1-p)
= p/n[1 + 2 + ... + i + ... + n] + n(1-p)
= p/n * n(n+1)/2 + n(1-p)
= p(n+1) / 2 + n(1-p)
由此可知，
- 如果
p = 1崇渗，也就是說(shuō)成功率是 100%字逗，查找一定能成功京郑，代入公式可得(n+1)/2，即大約要查找數(shù)組中一半的元素葫掉； - 如果
p = 0些举，也就是說(shuō)成功率是 0%，查找必定失敗俭厚，代入公式可得n户魏，即算法會(huì)對(duì)所有元素全部查找一遍。
從這個(gè)例子可以發(fā)現(xiàn)挪挤，平均效率的研究要比最差效率和最優(yōu)效率的研究困難很多：
我們要將輸入規(guī)模 n 劃分為幾種類型叼丑，對(duì)于同類型的輸入，使得算法的執(zhí)行次數(shù)是相同的扛门。
結(jié)束：
算法是計(jì)算機(jī)科學(xué)的基礎(chǔ)鸠信，以后會(huì)繼續(xù)更新算法相關(guān)的隨筆，對(duì)算法感興趣的朋友歡迎關(guān)注本博客尖飞，也歡迎大家留言討論症副。
我們正處于大數(shù)據(jù)時(shí)代，對(duì)數(shù)據(jù)處理感興趣的朋友歡迎查看另一個(gè)系列隨筆：
利用Python進(jìn)行數(shù)據(jù)分析 基礎(chǔ)系列隨筆匯總
參考資料：
Introduction to The Design and Analysis of Algorithms, Third Edition by Anany Leitin
