lec1:算法分析——以插入排序和归并排序为例

lec1-算法导论算法分析插入排序渐近分析归并排序递归式【算法】定义明确的计算过程接收一个或一组值作为输入经过一系列计算步骤将输入转换为一个或一组值作为输出。简单来说算法就是一套能把输入变成输出的、清晰且可执行的步骤。插入排序 Insertion sort伪代码如下INSERTION-SORT(A)forj2to A.length keyA[j]// 取出当前要插入的元素 // 将 A[j]插入到已排序的序列 A[1..j-1]中 ij -1whilei0and A[i]key A[i1]A[i]// 比key大的元素向后移动一位 ii -1A[i1]key // 将key插入到正确位置插入排序好比“抓牌”手里握着的是前j-1即i张牌已经排好序的接下来每抓一张牌就和第i张牌比较。如果比i牌大就放在i1的位置如果比i牌小则i牌后移把这张新牌插进去以此类推……直至j张牌有序。示例如上。运行时间T(n)T(n) 每行代码执行的次数 * 该行代码的单位时间注意for循环最后还要判断一次条件不成立tj表示第j次外层循环时while的循环次数。T(n) c1nc2(n-1)c4(n-1)c5∑j2ntj\sum_{j2}^n t_j∑j2n​tj​c6∑j2n(tj−1)\sum_{j2}^n (t_j-1)∑j2n​(tj​−1)c7∑j2n(tj−1)\sum_{j2}^n (t_j-1)∑j2n​(tj​−1)c8(n-1)最好情况已经拍好序了不用后移。(tj 1)T(n) (c1c2c4c5c8)n - (c2c4c5c8)最坏情况数组逆序每次移动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(c1c2c4c 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 - (c2c4c5c8)平均情况算法在规模为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)之间。注意丢弃低阶项忽略首项系数插入排序的时间复杂度分析Tn Θ(n2)插入排序适合小规模的排序大规模排序完全不适用归并排序分支思想如果n 1,已完成递归划分成两个子数组合并子数组示例如上T(n){Θ(1),n12T(n/2)Θ(n),n1 T(n)\begin{cases}Θ(1), n 1 \\ 2T(n/2)Θ(n) , n1 \end{cases}T(n){Θ(1),2T(n/2)Θ(n),​n1n1​递归树递归树求解归并排序的递归式总结归并排序在最坏情况下渐近性能优于插入排序。n30