本系列文章根据MIT公开课程：算法导论，并结合《算法导论》进行整理。
Analysis of algorithm 算法分析
关于计算机程序在效率和资源利用方面的理论研究
首先提出几个问题？
有比效率更重要的吗？
其实有很多，例如：正确性、可维护性、时间成本、健壮性、用户友好（user-friendly）等等既然如此，为什么还要进行算法的效率分析呢？
一个很有意思的比方，你认为钱重要还是水和饭重要？当然是水和饭，但是钱却可以换来水和饭。在算法分析中的“效率”，就是用来支持其他东西的基础，比如用户体验、安全等等。
这里举个例子：排序问题
Input：一些列的数字集合 seq<a1, a2, a3... an>
Output：重新排序的数字集合seq<a1', a2', a3'... an'>，并且a1'<a2'<a3'...<an'
插入排序实现（伪代码）：
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]的位置即可
归并排序实现（伪代码）：
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
将一个表分成两部分递归排序，递归处理的两个表已经有序了后进行合并
关注运行时间，依赖于
-数据的输入情况，数据是否有序
-数据的规模
-找到运行时间上界。一般情况下，我们需要找到这个程序对于最坏的输入数据的情况下，运行时间是多长。As a guarantee to the user
几种分析运行时间的方法
Worst-case:(usually)
用T(n)来表示算法在输入规模为n时的最大运行时间
Average-case:(sometimes)
用T(n)来表示算法在所有输入规模为n的序列的运行时间的一个期望值。
基于假设：输入的统计分布，一种常见的假设就是均匀分布，所有输入都以相同可能的方式出现。
Best-case:(bogus)
用一组极好的数据在一个效率极低的算法上跑，没有说服力。
那么插入排序的Worst-case时间是多少？
首先取决于运行的机器，所以当比较算法时，通常比较的是相对速度（在同一台机器上）
Big Idea——引入渐近分析
忽略那些依赖于机器的常量
关注当n趋近于无限大时，T(n)的增长
渐进符号（Asymptotic notation）
θ-notation：忽略所有的低阶项和常数因子，只分析最高阶项
3n3 + 2n2 + 4n + 1=θ(n3)
如果算法A的渐近时间复杂度是θ(n3)，算法B的是θ(n2)，那么一定存在一个足够大的n，算法B的运行时间要小于A
对于插入排序的分析
T(n)=Σθ(j)=θ(n2)
所以插入排序够快吗？
当n比较小的时候比较快，但是当n变大时效率会很糟糕
对于归并排序的分析
T(n)=2T(n/2)+θ(n)=2T(n/2)+cn=θ(nlgn) | constant c > 0
归并排序能够在效率上当输入规模n增大的时候渐近的超过插入排序，在最坏的情况下。实际上，当n>30以及以上的时候，归并排序的效率就比插入排序的效率要高了
