lec1-算法导论
算法分析：插入排序，渐近分析，归并排序，递归式
【算法】：定义明确的计算过程，接收一个或一组值作为输入，经过一系列计算步骤将输入转换为一个或一组值作为输出。
简单来说，算法就是一套能把输入变成输出的、清晰且可执行的步骤。
插入排序 Insertion sort
伪代码如下：
INSERTION-SORT(A)forj=2to A.length key=A[j]// 取出当前要插入的元素 // 将 A[j]插入到已排序的序列 A[1..j-1]中 i=j -1whilei>0and A[i]>key A[i+1]=A[i]// 比key大的元素向后移动一位 i=i -1A[i+1]=key // 将key插入到正确位置插入排序好比“抓牌”，手里握着的是前
j-1即i张牌（已经排好序的），接下来每抓一张牌，就和第i张牌比较。
如果比i牌大，就放在i+1的位置；如果比i牌小，则i牌后移，把这张新牌插进去，以此类推……直至j张牌有序。
示例如上。
运行时间T(n)
T(n) = 每行代码执行的次数 * 该行代码的单位时间
注意：for循环最后还要判断一次条件不成立；tj表示第j次外层循环时while的循环次数。
T(n) = c1n+c2(n-1)+c4(n-1)+c5∑j=2ntj\sum_{j=2}^n t_j∑j=2ntj+c6∑j=2n(tj−1)\sum_{j=2}^n (t_j-1)∑j=2n(tj−1)+c7∑j=2n(tj−1)\sum_{j=2}^n (t_j-1)∑j=2n(tj−1)+c8(n-1)
最好情况：已经拍好序了，不用后移。(tj= 1)
T(n) = (c1+c2+c4+c5+c8)n - (c2+c4+c5+c8)
最坏情况：数组逆序，每次移动j-1个位。(tj= j)
T(n) = (c 5 2\frac{c~5~}{2}2c5+c 6 2\frac{c~6~}{2}2c6+c 7 2\frac{c~7~}{2}2c7)n2+(c1+c2+c4+c 5 2\frac{c~5~}{2}2c5-c 6 2\frac{c~6~}{2}2c6-c 7 2\frac{c~7~}{2}2c7+c8)n - (c2+c4+c5+c8)
平均情况：算法在规模为n的所有输入下的期望运行时间。
与机器无关的时间分析——渐近分析
Θ(g(n))表示一个函数集合：
Θ(g(n))={f(n):存在正常数 c1,c2,n0，使得对所有 n≥n0，有 0≤c1≤g(n)≤f(n)≤c2g(n)}
当n足够大时，f(n)的增长速度和g(n)同阶，被夹在c1g(n)和c2g(n)之间。
注意：丢弃低阶项；忽略首项系数
插入排序的时间复杂度分析
T（n）= Θ(n2)
插入排序适合小规模的排序，大规模排序完全不适用！
归并排序
分支思想
- 如果n = 1,已完成；
- 递归划分成两个子数组；
- 合并子数组
示例如上
T(n)={Θ(1),n=12T(n/2)+Θ(n),n>1 T(n)=\begin{cases}Θ(1), & n = 1 \\ 2T(n/2)+Θ(n) , & n>1 \end{cases}T(n)={Θ(1),2T(n/2)+Θ(n),n=1n>1
递归树
递归树求解归并排序的递归式
总结
归并排序在最坏情况下渐近性能优于插入排序。（n>30）
