本系列文章根據(jù)MIT公開課程：算法導(dǎo)論，并結(jié)合《算法導(dǎo)論》進(jìn)行整理。
Analysis of algorithm 算法分析
關(guān)于計算機(jī)程序在效率和資源利用方面的理論研究
首先提出幾個問題？
有比效率更重要的嗎？
其實有很多，例如：正確性、可維護(hù)性、時間成本、健壯性、用戶友好（user-friendly）等等既然如此，為什么還要進(jìn)行算法的效率分析呢？
一個很有意思的比方，你認(rèn)為錢重要還是水和飯重要？當(dāng)然是水和飯，但是錢卻可以換來水和飯。在算法分析中的“效率”，就是用來支持其他東西的基礎(chǔ)，比如用戶體驗、安全等等。
這里舉個例子：排序問題
Input：一些列的數(shù)字集合 seq<a1, a2, a3... an>
Output：重新排序的數(shù)字集合seq<a1', a2', a3'... an'>，并且a1'<a2'<a3'...<an'
插入排序?qū)崿F(xiàn)（偽代碼）：
insertion sort(A[1...n])
for j <- 2 to n
do key <- A[j]
i <- j-1
while i>0 and A[i]>key
do A[i+1] <- A[i]
i <- i-1
A[i+1] <- key
對于每一個A[i]，考慮A[1...i-1]中它的合適的插入位置k，然后將A[k...i-1]依次后移一個位置，把A[i]插入到A[k]的位置即可
歸并排序?qū)崿F(xiàn)（偽代碼）：
merge sort(A[1...n])
1. if n=1 done
2. recursively sort A[1...n/2] and A[n/2+1...n]
3. merge 2 sorted lists
將一個表分成兩部分遞歸排序，遞歸處理的兩個表已經(jīng)有序了后進(jìn)行合并
關(guān)注運行時間，依賴于
-數(shù)據(jù)的輸入情況，數(shù)據(jù)是否有序
-數(shù)據(jù)的規(guī)模
-找到運行時間上界。一般情況下，我們需要找到這個程序?qū)τ谧顗牡妮斎霐?shù)據(jù)的情況下，運行時間是多長。As a guarantee to the user
幾種分析運行時間的方法
Worst-case:(usually)
用T(n)來表示算法在輸入規(guī)模為n時的最大運行時間
Average-case:(sometimes)
用T(n)來表示算法在所有輸入規(guī)模為n的序列的運行時間的一個期望值。
基于假設(shè)：輸入的統(tǒng)計分布，一種常見的假設(shè)就是均勻分布，所有輸入都以相同可能的方式出現(xiàn)。
Best-case:(bogus)
用一組極好的數(shù)據(jù)在一個效率極低的算法上跑，沒有說服力。
那么插入排序的Worst-case時間是多少？
首先取決于運行的機(jī)器，所以當(dāng)比較算法時，通常比較的是相對速度（在同一臺機(jī)器上）
Big Idea——引入漸近分析
忽略那些依賴于機(jī)器的常量
關(guān)注當(dāng)n趨近于無限大時，T(n)的增長
漸進(jìn)符號（Asymptotic notation）
θ-notation：忽略所有的低階項和常數(shù)因子，只分析最高階項
3n3 + 2n2 + 4n + 1=θ(n3)
如果算法A的漸近時間復(fù)雜度是θ(n3)，算法B的是θ(n2)，那么一定存在一個足夠大的n，算法B的運行時間要小于A
對于插入排序的分析
T(n)=Σθ(j)=θ(n2)
所以插入排序夠快嗎？
當(dāng)n比較小的時候比較快，但是當(dāng)n變大時效率會很糟糕
對于歸并排序的分析
T(n)=2T(n/2)+θ(n)=2T(n/2)+cn=θ(nlgn) | constant c > 0
歸并排序能夠在效率上當(dāng)輸入規(guī)模n增大的時候漸近的超過插入排序，在最壞的情況下。實際上，當(dāng)n>30以及以上的時候，歸并排序的效率就比插入排序的效率要高了
