算法基础笔记 原生生物 *顾乃杰老师算法基础课堂笔记[以幸开头的行代表动机与注释等，*开头的行代表补充内容] 目录 一算法概念与数学基础 51.1算法简介与分析 。……·。。。。。。。·。。。。。。。…。。。。。…4·。。 2 12设计算法。··········。····················· 13渐进记号与递归。······························ 51.4判断方法 515摊还分析..···.··.·。·，.·.。。，。···.·.·..···. 二排序与顺序统计 8 521简单排序与希尔排序.。。。·.··。。.。。.。.。。···。.。。··.. 9 9 52.3快速排序 52.4线性时间排序 。。。e4。。。。+0。。。。。4。。44。。。g4。。 13 三算法设计基本策略 14 16 53.4分治策略案例·····。··。······················· 2 §3.5快速傅里叶变换 21 四数据结构 54.1二分检索树 2 54.2红黑树 54.3动态顺序统计······，······················ 2 54.4斐波那契堆... 545分离集合····························· 31 五图论算法与串匹配 32 55.1图的表示与遍历 52图论问题。······························· 1
算法基础 笔记 原生生物 *顾乃杰老师算法基础课堂笔记 [以 * 开头的行代表动机与注释等，** 开头的行代表补充内容] 目录 一 算法概念与数学基础 2 §1.1 算法简介与分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 §1.2 设计算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 §1.3 渐进记号与递归 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 §1.4 判断方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 §1.5 摊还分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 二 排序与顺序统计 8 §2.1 简单排序与希尔排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 §2.2 堆排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 §2.3 快速排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 §2.4 线性时间排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 §2.5 中位数与顺序统计 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 三 算法设计基本策略 14 §3.1 动态规划 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 §3.2 更多例子 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 §3.3 贪心算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 §3.4 分治策略案例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 §3.5 快速傅里叶变换 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 四 数据结构 22 §4.1 二分检索树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 §4.2 红黑树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 §4.3 动态顺序统计 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 §4.4 斐波那契堆 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 §4.5 分离集合 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 五 图论算法与串匹配 32 §5.1 图的表示与遍历 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 §5.2 图论问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 §5.3 串匹配算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 1
一算法概念与数学基础 一算法概念与数学基础 定义：输入-》算法->输出 可计算问题[computational problem]:对输入输出要求的说明 问题的实例[instance]:某个求解需要的具体输入 (排序算法中，粉入数组、输出排好的数组是问题，而一个具体的乱序数组则是实例) 正确性：要求对任何输入能正确给出输出（随机算法可能一定程度违反） 学习算法的意义：确定解决方式的正确性、选择容易实现的算法，比较时空复杂度 *算法效率比电脑速度更重要 51.1算法简介与分析 伪代码书写：注重表达清楚，不关注语言细节 约定：缩进表示块结构、循环结构与C类似解释、/代表注释、变量如无特殊说明表示局部变量 举例：插入排序（就地[in-place]排序，需要的额外空间为O(1),即常量） def INTERSECTION-SORT(A): for (j0 and A[i]key) A[i+1]<-A[i] 1父-1-1 A[i+1]<-key *如何证明正确性？ 可选方法：循环不变式[loop1 nvariant],保证初始化、选代时均为真（类似归纳），循环终止时能提 供有用性质（局限性：只能用于判断循环，无法判断分支等） 插入排序中不变式：A[1.j-1]在循环后有序 ◆现实：理论证明几乎无法做到，通过大量测试假定正确 幸*关于正确性[correctness]:正确性指算法在程序规范下被认定为正确的判定，其中功能[functi- conal】正确针对输入输出的行为，一般分为部分[partial】正确与完全[total】正确，前者指输出 结果时结果正确，后者还额外要求必须能输出结果。 算法分析 含义：预测算法需要的资源，通常关心时间[computational time]与内存空间[memory,偶尔会涉 及通信带宽、硬件使用等 为了统一评价，需要使用统一、简洁的计算模型 *对串行算法一般使用RAM模型[Random-access machine],并行则为PRAM模型[Parallel RAM] RAM模型特点： 1.指令一条条执行（不存在并发）
一 算法概念与数学基础 2 一 算法概念与数学基础 定义：输入‐> 算法‐> 输出 可计算问题 [computational problem]：对输入输出要求的说明 问题的实例 [instance]：某个求解需要的具体输入 (排序算法中，输入数组、输出排好的数组是问题，而一个具体的乱序数组则是实例) 正确性：要求对任何输入能正确给出输出 (随机算法可能一定程度违反) 学习算法的意义：确定解决方式的正确性、选择容易实现的算法，比较时空复杂度 *算法效率比电脑速度更重要 §1.1 算法简介与分析 伪代码书写：注重表达清楚，不关注语言细节 约定：缩进表示块结构、循环结构与 C 类似解释、//代表注释、变量如无特殊说明表示局部变量 举例：插入排序 (就地 [in‐place] 排序，需要的额外空间为 O(1)，即常量) def INTERSECTION‐SORT(A): for (j 0 and A[i] > key) A[i+1] <‐ A[i] i <‐ i ‐ 1 A[i+1] <‐ key *如何证明正确性？ 可选方法：循环不变式 [loop invariant]，保证初始化、迭代时均为真 (类似归纳)，循环终止时能提 供有用性质 (局限性：只能用于判断循环，无法判断分支等) 插入排序中不变式：A[1..j‐1] 在循环后有序 *现实：理论证明几乎无法做到，通过大量测试假定正确 **关于正确性 [correctness]：正确性指算法在程序规范下被认定为正确的判定，其中功能 [functi‐ conal] 正确针对输入输出的行为，一般分为部分 [partial] 正确与完全 [total] 正确，前者指输出 结果时结果正确，后者还额外要求必须能输出结果。 算法分析 含义：预测算法需要的资源，通常关心时间 [computational time] 与内存空间 [memory]，偶尔会涉 及通信带宽、硬件使用等 为了统一评价，需要使用统一、简洁的计算模型 *对串行算法一般使用 RAM 模型 [Random‐access machine]，并行则为 PRAM 模型 [Parallel RAM] RAM 模型特点： 1. 指令一条条执行 (不存在并发)
一算法概念与教学基础 2.包含常见算数指令、数据移动指令、控制指令，且指令所需时间为常量 *按照真实计算机设定，不应滥用 *特殊情况：如一般指数运算不是常量时间，但2通过左移可常量时间 3.数据类型有整数与浮点 *不关心精度 4.假定数据字的规模存在范围，字长不能任意长 *不关心内存层次（高速缓存、虚拟内存） 影响运行时间的主婴因素 1.输入规模 2.输入数据的分布 *将算法运行时间描述成输入规模的函数 3.算法实现所选用的底层数据结构 *思考：RAM模型中其他影响因素？ *输入规模与运行时间如何严谨定义 输入规模[input size]:对许多问题为输入项的个数（如排序），但有时（如整数相乘）关心的是二进 制表示的总位数，有时则用两个数表示更合适（图的顶点数与边数） *必须描述清楚输入规模的量度 运行时间[running time]:执行的基本操作数或步数，与机器无关，一般假设每行伪代码恒定时间 ◆实际计算时，由于循环嵌套所需的步数不同，很可能较为复杂，于是需要二次抽象[最终将系数抽象为 独立于数据规檬的常数，只关心量级 最好/最坏运行时间：最快/最慢情况的运行时间（插入排序的例子中，最好为0(），最坏为O(2) 平均运行时间：运行时间在所有输入下的期望值（与数据的概率分布有关，一股默认均匀一致分布，插入 排序的例子中为On2)) *平均V5最坏：最好运行时间的参考意义不大，而平均运行时间往往非常难以计算，因此一般采取最坏运 行时间[事实上平均运行时间往往和最坏运行时间量级相同]。最坏运行时间给定了运行时间的上界，课 程中主要讨论最坏，偶尔讨论平均。 51.2设计算法 分治、贪婪、动态规划、线性规划、回溯、分支定界… 分治[divide-and-conquer】法：分解[Divide]、解决[Conquer]?、合并[Combine] 举例：归并排序（分解成子序列，对子序列排序后合成） def MergeSort(A,p,r): if(p<r) q<-(p+r)/2 MergeSort(A,p,q) MergeSort(A,q+1,r)
一 算法概念与数学基础 3 2. 包含常见算数指令、数据移动指令、控制指令，且指令所需时间为常量 *按照真实计算机设定，不应滥用 *特殊情况：如一般指数运算不是常量时间，但 2 k 通过左移可常量时间 3. 数据类型有整数与浮点 *不关心精度 4. 假定数据字的规模存在范围，字长不能任意长 *不关心内存层次 (高速缓存、虚拟内存) 影响运行时间的主要因素： 1. 输入规模 2. 输入数据的分布 *将算法运行时间描述成输入规模的函数 3. 算法实现所选用的底层数据结构 *思考：RAM 模型中其他影响因素？ *输入规模与运行时间如何严谨定义？ 输入规模 [input size]：对许多问题为输入项的个数 (如排序)，但有时 (如整数相乘) 关心的是二进 制表示的总位数，有时则用两个数表示更合适 (图的顶点数与边数) *必须描述清楚输入规模的量度 运行时间 [running time]：执行的基本操作数或步数，与机器无关，一般假设每行伪代码恒定时间 *实际计算时，由于循环嵌套所需的步数不同，很可能较为复杂，于是需要二次抽象 [最终将系数抽象为 独立于数据规模的常数，只关心量级] 最好/最坏运行时间：最快/最慢情况的运行时间 (插入排序的例子中，最好为 O(n)，最坏为 O(n 2 )) 平均运行时间：运行时间在所有输入下的期望值 (与数据的概率分布有关，一般默认均匀一致分布，插入 排序的例子中为 O(n 2 )) *平均 vs 最坏：最好运行时间的参考意义不大，而平均运行时间往往非常难以计算，因此一般采取最坏运 行时间 [事实上平均运行时间往往和最坏运行时间量级相同]。最坏运行时间给定了运行时间的上界，课 程中主要讨论最坏，偶尔讨论平均。 §1.2 设计算法 分治、贪婪、动态规划、线性规划、回溯、分支定界…… 分治 [divide‐and‐conquer] 法：分解 [Divide]、解决 [Conquer]、合并 [Combine] 举例：归并排序 (分解成子序列，对子序列排序后合成) def MergeSort(A,p,r): if(p < r) q <‐ (p + r) / 2 MergeSort(A,p,q) MergeSort(A,q+1,r)
算法概念与数学基础 4 Merge(A,p,q,r) def Merge(A,P,q,r): n1=q-p+1; n2 =r -q LetL「1，，n1+11,R[1..n2+11 be new arrays for i <-1 to n1 L[i]<-A[p+i-1] for j<-1 to n2 R[j]<-A[q+j] L[n1+1]<-R[n2+1]<-INFTY[监视哨) 1<-j<-1 for k <-p to r if L[i]<R[j] A[k]<-L[i] 1++ else A[k]<-Rj】 j++ 采用无穷大作监视哨游免讨多判惭（注意：一定要保证东分大） *Merge算法正确性：迭代时子数组A[p.k-1]按从小到大的顺序包含B[1.n1+1]与C[1.n2+1] 中的k-D个最小元素 分析基于分治法的算法：递归式、递归方程 设T(n)是规模为n的运行时间（当n在某个常数之下时可当作常数） 假设分解为a个子问题，每个的规模是原本1/b,分解所需时间为D(n),合并所需时间为C(),则总 时间为： Θ) n<c T(n)= aT(n/b)+D(n)+C(n)otherwise 对归并排序：T()= 2/+6)otherwise.事实上复杂度为6a1og 1) n<e 思考： (1)自底向上[buttom-up]通过两两归并也可实现归并排疗 (2)如何使数组A[0.n-1]循环左移k位？ 法一：颠倒g到k-1、颠倒k到n-1、颠倒日到n-1(约3n次内容读写) 法二：思路：把置换拆分成轮换进行（约n次内容读写） d <-gcd(n,k) for i<-e to d-1 x <-A[i] t《-i for i<-1 to n/d-1
一 算法概念与数学基础 4 Merge(A,p,q,r) def Merge(A,p,q,r): n1 = q ‐ p + 1; n2 = r ‐ q Let L[1..n1+1],R[1..n2+1] be new arrays for i <‐ 1 to n1 L[i] <‐ A[p+i‐1] for j <‐ 1 to n2 R[j] <‐ A[q+j] L[n1+1] <‐ R[n2+1] <‐ INFTY [监视哨] i <‐ j <‐ 1 for k <‐ p to r if L[i] <= R[j] A[k] <‐ L[i] i++ else A[k] <‐ R[j] j++ *采用无穷大作监视哨避免过多判断 (注意：一定要保证充分大) *Merge 算法正确性：迭代时子数组 A[p..k‐1] 按从小到大的顺序包含 B[1..n1+1] 与 C[1..n2+1] 中的 k‐p 个最小元素 分析基于分治法的算法：递归式、递归方程 设 T(n) 是规模为 n 的运行时间 (当 n 在某个常数之下时可当作常数) 假设分解为 a 个子问题，每个的规模是原本 1/b，分解所需时间为 D(n)，合并所需时间为 C(n)，则总 时间为： T(n) = Θ(1) n < c aT(n/b) + D(n) + C(n) otherwise. 对归并排序：T(n) = Θ(1) n < c 2T(n/2) + Θ(n) otherwise. ，事实上复杂度为 Θ(n log n) 思考： (1) 自底向上 [buttom‐up] 通过两两归并也可实现归并排序 (2) 如何使数组 A[0..n‐1] 循环左移 k 位？ 法一：颠倒 0 到 k‐1、颠倒 k 到 n‐1、颠倒 0 到 n‐1 (约 3n 次内容读写) 法二：思路：把置换拆分成轮换进行 (约 n 次内容读写) d <‐ gcd(n,k) for i <‐ 0 to d‐1 x <‐ A[i] t <‐ i for j <‐ 1 to n/d‐1
一算法概念与教学基础 A[t]nn时01,f()）是某给定函数（并非对 何都可解)
一 算法概念与数学基础 5 A[t] 1，f(n) 是某给定函数 (并非对任 何都可解))
一算法概念与数学基础 6 *技术细节： 1.假定自变量整数，忽略上下取整。 2.对足够小的n假设T(m)为常数，忽略边界。 (一些特殊情况可能导致技术细节非常重要，上面两种条件仍然值得重视) 3.有时会存在不等式情况，如T(m)≤2T(n/2)+0(),此时一般用0描述上界，反之对大于等于可 用2描述下界。 例：最大子数组问题（给定数组，求和最大的连续子数组） 分治策略：找到数组中央位置，任何连续子数组必然在其左侧、右侧，或包含它。左侧与右侧可直接通过 递归，由此只需要找到包含中间位置的最大子数组后取最大值即可。 def find_max_crossing_subarray(A,low,mid,high): left_sum=-INFTY for i=mid downto low sum +Alil if (sum left_sum) left sum sum max_left i right_sum =-INFTY sum =e for i=mid->low sum +A[i] if (sum right_sum) right_sum =sum max right i return(max_left,max_right,left_sum+right_sum) 整体算法：利用上方的算法进行递归，low=high即为终止条件。 复杂度分析：包含中间位置的部分的复杂度为(，递归方程为T()= n=1 2T(n/2)+0(n)otherwise. 可发现复杂度与归并排序相同，为6(nlogn)。 *算法改进（Θ(n)算法）：从左侧开始，找到第一个大于日的位置i1开始，依次求和(sum+=A[]), max1记录目前的最大值，并记录当前的j1。直到Sum<日时中止，然后继续向右找到下一个大于日的 位置i2,清空5Um,重复此过程，在比较中得到maxk中的最大值即可（证明思路：反证，若否则可以 拼接为更大)。 def find_max_subarray(A,low,high): now <low sum <-0 max <--INFTY
一 算法概念与数学基础 6 **技术细节： 1. 假定自变量整数，忽略上下取整。 2. 对足够小的 n 假设 T(n) 为常数，忽略边界。 (一些特殊情况可能导致技术细节非常重要，上面两种条件仍然值得重视) 3. 有时会存在不等式情况，如 T(n) ≤ 2T(n/2) + O(n)，此时一般用 O 描述上界，反之对大于等于可 用 Ω 描述下界。 例：最大子数组问题 (给定数组，求和最大的连续子数组) 分治策略：找到数组中央位置，任何连续子数组必然在其左侧、右侧，或包含它。左侧与右侧可直接通过 递归，由此只需要找到包含中间位置的最大子数组后取最大值即可。 def find_max_crossing_subarray(A,low,mid,high): left_sum = ‐INFTY sum = 0 for i = mid downto low sum += A[i] if (sum > left_sum) left_sum = sum max_left = i right_sum = ‐INFTY sum = 0 for i = mid ‐> low sum += A[i] if (sum > right_sum) right_sum = sum max_right = i return (max_left, max_right, left_sum+right_sum) 整体算法：利用上方的算法进行递归，low=high 即为终止条件。 复杂度分析：包含中间位置的部分的复杂度为 Θ(n)，递归方程为 T(n) = Θ(1) n = 1 2T(n/2) + Θ(n) otherwise. ， 可发现复杂度与归并排序相同，为 Θ(n log n)。 *算法改进 (Θ(n) 算法)：从左侧开始，找到第一个大于 0 的位置 i1 开始，依次求和 (sum+=A[j])， max1 记录目前的最大值，并记录当前的 j1。直到 sum<0 时中止，然后继续向右找到下一个大于 0 的 位置 i2，清空 sum，重复此过程，在比较中得到 maxk 中的最大值即可 (证明思路：反证，若否则可以 拼接为更大)。 def find_max_subarray(A, low, high): now <‐ low sum <‐ 0 max <‐ ‐INFTY
一算法概念与教学基础 for now ) max_now T2)+1即可 更复杂的例子：求T(m)=2T(n/2+17)+n的解的上界。 解法（平移的思路）：令n=m+34,可发现T(m+34)=2T(Lm/2+34)+m+34,由此T(m+34)+34= 2(T(m/2+34+34)+m类似上一种情况可直接估算出上界。 ◆猜测出渐近界未必能归纳成功，有时是因为归纳假设偏弱，可以尝试加强假设、调整低阶项、初等变换 等，如T()=2T(ln/2)+1,归纳假设cm无法继续，假设为m-2即可。 ◆不应将猜测无理由放大 *变量代换：对T(n)=2T(lV)+1ogm,取m=1ogn可发现最终结果为0(1ogn1og1ogm). **弊端：猜测、证明都可能困难 递归树 每个结点代表相应子问题代价，行和代表某层代价，总和得总代价 ◆一般用来获得猜测解再替代，省略大部分细节。也可细化直接解出结果。 例：T(m)=3T(ln/个)+Θ(n)→T(m)=3T(n/④+cm2简化，接着画出递归树求得复杂度大约为 ∑6cm2=cn2,因此为6(n2)量级 代价不相同：T(m)=T/3)+T(2n/3)+O(,作出递归树可发现每层的和为cm,再由行数（通过解方 程可计算出层数具体值，不过估算中没有精确必要)为O(1og)可知复杂度O(n1ogm)。同理，对于 T(m)=T(n/纠+T(/2)+n2,可类似算得结果为等比级数的n2倍，仍为n2量级。 *关健为求行和与总代价，需要上下行和的关联 主方法
一 算法概念与数学基础 7 for now 0) sum += A[now] if (sum > max_now) j_now max) i_max 0) max_now T(2) + 1 即可。 更复杂的例子：求 T(n) = 2T(⌊n/2⌋ + 17) + n 的解的上界。 解法 (平移的思路)：令 n = m+34，可发现 T(m+34) = 2T(⌊m/2⌋+34)+m+34，由此 T(m+34)+34 = 2(T(⌊m/2⌋ + 34) + 34) + m 类似上一种情况可直接估算出上界。 *猜测出渐近界未必能归纳成功，有时是因为归纳假设偏弱，可以尝试加强假设、调整低阶项、初等变换 等，如 T(n) = 2T(⌊n/2⌋) + 1，归纳假设 cn 无法继续，假设为 cn − 2 即可。 *不应将猜测无理由放大 *变量代换：对 T(n) = 2T(⌊ √ n⌋) + log n，取 m = log n 可发现最终结果为 O(log n log log n)。 **弊端：猜测、证明都可能困难 递归树 每个结点代表相应子问题代价，行和代表某层代价，总和得总代价 *一般用来获得猜测解再替代，省略大部分细节。也可细化直接解出结果。 例：T(n) = 3T(⌊n/4⌋) + Θ(n 2 ) =⇒ T(n) = 3T(n/4) + cn2 简化，接着画出递归树求得复杂度大约为 ∑∞ i=0 3 i 16i cn2 = c ′n 2，因此为 Θ(n 2 ) 量级。 代价不相同：T(n) = T(n/3) + T(2n/3) + O(n)，作出递归树可发现每层的和为 cn，再由行数 (通过解方 程可计算出层数具体值，不过估算中没有精确必要) 为 O(log n) 可知复杂度 O(n log n)。同理，对于 T(n) = T(n/4) + T(n/2) + n 2，可类似算得结果为等比级数的 n 2 倍，仍为 n 2 量级。 *关键为求行和与总代价，需要上下行和的关联 主方法
二排序与顺序统计 6 主要适用范围：Tm)=aT(m/)+fm,其中a≥1，b>1,f渐近非负。 主定理[The master theorem]):若fn)=O(nioga-c),e>0,则T(n)=0(nloa):若f(n)= 0(ma1og,则T(m)=6(noa1og+1n:若fm）=2(mlo8-),e>0,且af(n/)≤cf(m) 则T(m)=6(fm) *种情况存在间隙，可能无法判断（如T(m)=3T(n/3)+1og1ogn),并不代表递归方程无解 S1.5摊还分析 思路：考虑一系列操作的可能的最坏情况的平均复杂度为 *不涉及概率问题，与平均复杂度分析不同 例：栈操作 只有PUSH和POP时，视二者代价为1，则操作的平均代价必然为1。 在PUSH和POP上增添一个MULTIPOP(k),一次允许弹出多个元素（最多到栈底），其代价实际上为 min(s,k),其中s代表栈中元素。 *加入此操作后，n次操作的平均代价？ 虽然MULTIPOP的上限代价为Om,但由于最多入栈n次，出栈也最多n次，实际上平均代价仍为 0(1). 例：二进制计数器 k位二进制计数器，将每位的修改作为代价1。在允许加法时，一次加法最高需要修政k位，但是n次 的总代价可以估算为号+2婴+3爱+·=0()，于是平均代价仍为0(1)。 核算法[accounting method] 给每个操作赋予摊还代价，保证每次操作摊还代价的总和不小于实际代价（而当某步摊还代价比实际代价 大时，将其称为信用，用来支付之后的差额)。 *栈操作的例子中，PUSH的摊还代价为2，其余全为：对二进制计数器，假设日到1操作【置位] 的摊还代价为2,1到日操作[复位]的摊还代价为©，由于每次增加恰好产生一次置位，而复位时每 个为1的位都保留信用支付，因此可得到结论。 势能法[potential method] 对每个状态定义势函数[映射到实数]，一般初始状态为日。将摊还代价定义为代价+操作后的势-操作 前的势。 *栈操作的例子中，势为栈中元素个数：对二进制计数器，势为数中1的个数。可发现得到的摊还代价与 核算法中一致。 *通过势能法分析，当二进制计数器计数器不是从零开始时，这样的定义仍然合理，于是个操作的实际 代价为2n+bn-如，b为势函数。于是，充分大时平均复杂度仍然(1)。 二 排序与顺序统计 一些概念 稳定性：不论输入数据如何分布，关健字相同的数据对象（如两个3）在整个过程中保持相对位置不变 内排序/外排序：是/否在内存中进行 时间开销：通过比较次数与移动次数衡量 评价标准：所需时间[主要因素]、附加空间[一般都不大，矛盾不突出]、实现复杂程度
二 排序与顺序统计 8 主要适用范围：T(n) = aT(n/b) + f(n)，其中 a ≥ 1, b > 1，f 渐近非负。 主定理 [The master theorem]：若 f(n) = O(n logb a−ε ), ε > 0，则 T(n) = Θ(n logb a )；若 f(n) = O(n logb a logk n)，则 T(n) = Θ(n logb a logk+1 n)；若 f(n) = Ω(n logb a−ε ), ε > 0，且 af(n/b) ≤ cf(n)， 则 T(n) = Θ(f(n))。 *三种情况存在间隙，可能无法判断 (如 T(n) = 3T(n/3) + log log2 n)，并不代表递归方程无解 §1.5 摊还分析 思路：考虑一系列操作的可能的最坏情况的平均复杂度为 *不涉及概率问题，与平均复杂度分析不同 例：栈操作 只有 PUSH 和 POP 时，视二者代价为 1，则操作的平均代价必然为 1。 在 PUSH 和 POP 上增添一个 MULTIPOP(k)，一次允许弹出多个元素 (最多到栈底)，其代价实际上为 min(s,k)，其中 s 代表栈中元素。 *加入此操作后，n 次操作的平均代价？ 虽然 MULTIPOP 的上限代价为 O(n)，但由于最多入栈 n 次，出栈也最多 n 次，实际上平均代价仍为 O(1)。 例：二进制计数器 k 位二进制计数器，将每位的修改作为代价 1。在允许加法时，一次加法最高需要修改 k 位，但是 n 次 的总代价可以估算为 n 2 + 2 n 4 + 3 n 8 + · · · = O(n)，于是平均代价仍为 O(1)。 核算法 [accounting method] 给每个操作赋予摊还代价，保证每次操作摊还代价的总和不小于实际代价 (而当某步摊还代价比实际代价 大时，将其称为信用，用来支付之后的差额)。 *栈操作的例子中，PUSH 的摊还代价为 2，其余全为 0；对二进制计数器，假设 0 到 1 操作 [置位] 的摊还代价为 2，1 到 0 操作 [复位] 的摊还代价为 0，由于每次增加恰好产生一次置位，而复位时每 个为 1 的位都保留信用支付，因此可得到结论。 势能法 [potential method] 对每个状态定义势函数 [映射到实数]，一般初始状态为 0。将摊还代价定义为代价 + 操作后的势‐操作 前的势。 *栈操作的例子中，势为栈中元素个数；对二进制计数器，势为数中 1 的个数。可发现得到的摊还代价与 核算法中一致。 *通过势能法分析，当二进制计数器计数器不是从零开始时，这样的定义仍然合理，于是 n 个操作的实际 代价为 2n + bn − b0，b 为势函数。于是，充分大时平均复杂度仍然 O(1)。 二 排序与顺序统计 一些概念 稳定性：不论输入数据如何分布，关键字相同的数据对象 (如两个 3) 在整个过程中保持相对位置不变 内排序/外排序：是/否在内存中进行 时间开销：通过比较次数与移动次数衡量 评价标准：所需时间 [主要因素]、附加空间 [一般都不大，矛盾不突出]、实现复杂程度
二排序与顺序统计 52.1简单排序与希尔排序 直接插入、简单选择、冒泡 希尔排序：调用直接插入，不稳定，复杂度更低 *直接插入见第一章 简单选择：n-1遍处理，第1卷将a[i.n】中的最小元与a[1】交换。比较次数0(m2),移动次数最 多(n-1),平均时间复杂度0(m2)。需要常数额外空间，就地排序。存在跨格跳跃，分析可发现不稳定 冒泡：至多n-1遍处理，第1遍在a[i.]中依次比较，相邻交换，某次发现没有需要交换时结束。 比较次数O(n2),移动次数亦为最多O(2),平均时间复杂度O(n2)。稳定就地排序。 希尔[sh©1】排序：又称缩小增量排序，看作有增量的子列进行插入排序，对位置间隔较大的结点进行 比较以跨过较大距离。性能与增量序列有关，尽量避免序列中的值互为倍数，优于直接插入。 *最后一趟必须以1作为增量以保证正确 *由于几趟后接近分块有序，希尔排序的实际效率大大优于直接插入排序。复杂度分析非常困难，统计 结论一般时间复杂度在O(1.25)左右，而空间效率也很高。虽然如此，其理论最有复杂度亦无法达到 O(nlogn). def ShellPass(A,d): for i 0 and A[]A[]) A[j+d]<-A[j] j<-j-d A[j+d]<-A[e] def ShellSort(A,D): for i<-1 to length(D) ShellPass(A,D[i]) S2.2堆排序 堆[heap]排序：集中了归并排序与插入排序的优点，时间复杂度O(nlog,空间复杂度日(1)。使用 堆「h a即】数据结构，不止可以用在堆排序中，还可以构造另一种有效的数据结构：优先队列 *和内存的“堆”并不是同一个东西 (二叉)堆定义：树上每个结点对应数组中一个元素的完全二叉树，分为大根堆[父结点大于等于其任何 子结点]与小根堆【父结点小于等于其任何子结点]，排序算法中使用大根堆。 *表示堆的数组A有两个属性：数组元素个数[1 ength]与数组中属于堆的元素的个数[heapsize] heapsize<=length,数组的第一个元素代表根结点。 下标1开始的数组中，由于其为完全二叉树，可各层顺序排列，A[i]的父结点是[1/2]，左孩子21 右孩子21+1。 *[标准定义]满[ful1]二叉树：每层均为满：完全[complete】二叉树：最后一层的结点都在左侧， 未必满：严格[strict]二叉树：每个结点的孩子都为零个或两个 *0开始：A[1]的父结点是[(1-1)/2]，左孩子2i+1,右孩子2i+2。 结点高度：该结点到叶结点最长简单路径上边的数目（堆的高度：根结点的高度，为「1og,(n+1))
二 排序与顺序统计 9 §2.1 简单排序与希尔排序 直接插入、简单选择、冒泡 希尔排序：调用直接插入，不稳定，复杂度更低。 *直接插入见第一章 简单选择：n‐1 遍处理，第 i 遍将 a[i..n] 中的最小元与 a[i] 交换。比较次数 O(n 2 )，移动次数最 多 3(n − 1)，平均时间复杂度 O(n 2 )。需要常数额外空间，就地排序。存在跨格跳跃，分析可发现不稳定。 冒泡：至多 n‐1 遍处理，第 i 遍在 a[i..n] 中依次比较，相邻交换，某次发现没有需要交换时结束。 比较次数 O(n 2 )，移动次数亦为最多 O(n 2 )，平均时间复杂度 O(n 2 )。稳定就地排序。 希尔 [shell] 排序：又称缩小增量排序，看作有增量的子列进行插入排序，对位置间隔较大的结点进行 比较以跨过较大距离。性能与增量序列有关，尽量避免序列中的值互为倍数，优于直接插入。 *最后一趟必须以 1 作为增量以保证正确 *由于几趟后接近分块有序，希尔排序的实际效率大大优于直接插入排序。复杂度分析非常困难，统计 结论一般时间复杂度在 O(n 1.25) 左右，而空间效率也很高。虽然如此，其理论最有复杂度亦无法达到 O(n log n)。 def ShellPass(A,d): for i 0 and A[0] < A[j]) A[j+d] <‐ A[j] j <‐ j‐d A[j+d] <‐ A[0] def ShellSort(A,D): for i <‐ 1 to length(D) ShellPass(A,D[i]) §2.2 堆排序 堆 [heap] 排序：集中了归并排序与插入排序的优点，时间复杂度 O(n log n)，空间复杂度 Θ(1)。使用 堆 [heap] 数据结构，不止可以用在堆排序中，还可以构造另一种有效的数据结构：优先队列。 **和内存的“堆”并不是同一个东西 (二叉) 堆定义：树上每个结点对应数组中一个元素的完全二叉树，分为大根堆 [父结点大于等于其任何 子结点] 与小根堆 [父结点小于等于其任何子结点]，排序算法中使用大根堆。 *表示堆的数组 A 有两个属性：数组元素个数 [length] 与数组中属于堆的元素的个数 [heapsize]， heapsize<=length，数组的第一个元素代表根结点。 下标 1 开始的数组中，由于其为完全二叉树，可各层顺序排列，A[i] 的父结点是 [i/2]，左孩子 2i， 右孩子 2i+1。 *[标准定义] 满 [full] 二叉树：每层均为满；完全 [complete] 二叉树：最后一层的结点都在左侧， 未必满；严格 [strict] 二叉树：每个结点的孩子都为零个或两个 *0 开始：A[i] 的父结点是 [(i‐1)/2]，左孩子 2i+1，右孩子 2i+2。 结点高度：该结点到叶结点最长简单路径上边的数目 (堆的高度：根结点的高度，为 ⌈log2 (n + 1)⌉)
二排序与顺序统计 基本操作 维护堆：假定A[i]的左右子树都为大根堆，但A[1]有可能小于其孩子，则通过逐级下降使得下标为 1的根结点子树重新遵循大根堆， def MAX_HEAPIFY(A,i): 1=LEFT(i) r=RIGHT(i) if 1 <A.heap_size and A[l]A[i] Largest =1 else Largest i if r<=A.heap_size and A[r]A[Largest] Largest if (Largest !i) swap A[i],A[Largest] MAX_HEAPIFY(A,Largest) *每次至少下移一层，时间复杂度O(1og): 建堆：从后往前进行转化 一半处开始即可。 def BUILD MAX HEAP(A): A.Heap_size <-A.length for i<-[A.length/2]downto 1 MAX_HEAPIFY(A,i) *求和估算可知时间复杂度O(m) 堆排序：建好堆后，每次将根结点[当前最大]与最后一个元素互换，堆长度减小1，然后调整堆。 def HEAPSORT(A): BUILD MAX HEAP(A); for i<-length(A)downto 2 swap A[1],A[i] A.Heap size -1 MAX_HEAPIFY(A,1) 二叉堆的扩展：优先队列【并不是堆的基本操作！】 *用来维护一组元素构成的集合S的数据结构，每个元素都有一个相关值，称关键字[ky] 最大优先队列[可用大根堆构造】基本操作： 1.insert(S,x)插入元素进s
二 排序与顺序统计 10 基本操作 维护堆：假定 A[i] 的左右子树都为大根堆，但 A[i] 有可能小于其孩子，则通过逐级下降使得下标为 i 的根结点子树重新遵循大根堆。 def MAX_HEAPIFY(A, i): l = LEFT(i) r = RIGHT(i) if l A[i] Largest = l else Largest = i if r A[Largest] Largest = r if (Largest != i) swap A[i], A[Largest] MAX_HEAPIFY(A, Largest) *每次至少下移一层，时间复杂度 O(log n)。 建堆：从后往前进行转化，一半处开始即可。 def BUILD_MAX_HEAP(A): A.Heap_size <‐ A.length for i <‐ [A.length/2] downto 1 MAX_HEAPIFY(A, i) *求和估算可知时间复杂度 O(n)。 堆排序：建好堆后，每次将根结点 [当前最大] 与最后一个元素互换，堆长度减小 1，然后调整堆。 def HEAPSORT(A): BUILD_MAX_HEAP(A); for i <‐ length(A) downto 2 swap A[1], A[i] A.Heap_size ‐= 1 MAX_HEAPIFY(A, 1) 二叉堆的扩展：优先队列 [并不是堆的基本操作！] *用来维护一组元素构成的集合 S 的数据结构，每个元素都有一个相关值，称关键字 [key] 最大优先队列 [可用大根堆构造] 基本操作： 1. insert(S,x) 插入元素进 S
