《算法基础》课程教学资源（学习笔记）算法基础 课堂笔记

算法基础笔记 原生生物 *顾乃杰老师算法基础课堂笔记[以幸开头的行代表动机与注释等，*开头的行代表补充内容] 目录 一算法概念与数学基础 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 (j<-2)to length(A) key <-A[j] 1-j-1 while (i>0 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 <‐ 2) to length(A) key <‐ A[j] i <‐ j‐1 while (i > 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]<-A[(t+k) t<-(t+k)mod n A[t]<-x 51.3渐进记号与递归 f(m)=日(g(m)代表存在正常数C1,C2,o使得n≥o时0≤C1g(m)≤f(m≤C2g(n). *即趋于无穷时阶相同，9m)=Θ(f(》时亦有fm)=(g(》 一般证明中可以取较粗的C,C,0,不用解出精确的点 f(n)=O(a(n)代表存在正常数C.no使得n>nn时0<f(n)<Cg(n). *即趋于无穷时∫的阶不超过9，g()=日(f(m)时必有g(m)=O(f(n) fm=g(m)代表存在正常数C,o使得n≥o时0≤Cg(m)≤f(m *即趋于无穷时g的阶不超过∫，g(n)=6((m)时必有g(n)=(f(n》 f(m)=o(g(n)代表任意正常数c存在正常数o使得n≥o时0≤f(n)<cg(m)。 fm)=w(gn)代表任意正常数c存在正常数n使得n之n时0≤cg(m<fm): 大小写区别在存在与任意，也可以理解为大写剔除日 *实际使用时，O(f(n)可以代表某个满足g(n)=O(f(m)的g(n,这样的匿名[anonymous】函数可 以正常参与运算，但不应出现存在歧义的情况 渐进关系的性质： *五种关系都具有传递性 *6,0,2具有自反性 *日与日、0与、0与w互相置换对称 *不是任何两个函数都渐进可比，例如n与nl+1n,不存在O或？关系 上/下取整 取整性质：对正整数a,b,n,1=「品l,L」=品」 引理：fz)是连续单调上升函数，且整点处才取整值，则[fe川=[f([)几，L(x小=U(z)小 引理证明：对第一个式子，若[f1≠[f],由单调增可知fe)≤fx),从而[f(<[f(x门 由向上取整定义可知「f(x1<f(「l),而f(x)≤「f(x)l,从而「f(r1在f(x)与f(l)之间。由连 续定义知存在0使得f(o)=[f(x几，由条件知0必然为整数，但x≤0≤[z],其由向上取整定 义只能为「x,与[f1<[f(x矛盾。另一个式子同理。 定理证明：取fx)=,x=:即可。 其他数学：模、指数、对数、阶乘(Stirling公式)、函数选代(fm(x) *斐波那契[Fibonacci]数a1=2=1,an=an- +an-2,通项为方 *思考：服务器每隔g秒送包，拥有k个端口（同时发k个），收到的服务器需要花L秒时间解压，自 此每隔g秒给新服务器发送信息，时间与接受的服务器总数关系？（起初1对大兔子，大兔子每个隔g 个月可生k对小兔子，小兔子需要L个月成熟，求第n个月的兔子对数？)[广义斐波那契数] 递归介绍 *递归可能分解为规模不等的子问题 求解递归方程的方法：替代法（猜测上界后证明）、递归树法（转化成树，结点表示不同层次产生的代价， 再采用边界求和)、主方法（求解T()=aT/)+f),a≥1，b>1,f()）是某给定函数（并非对 何都可解)

一 算法概念与数学基础 5 A[t] <‐ A[(t+k) t <‐ (t+k) mod n A[t] <‐ x §1.3 渐进记号与递归 f(n) = Θ(g(n)) 代表存在正常数 C1, C2, n0 使得 n ≥ n0 时 0 ≤ C1g(n) ≤ f(n) ≤ C2g(n)。 *即趋于无穷时阶相同，g(n) = Θ(f(n)) 时亦有 f(n) = Θ(g(n)) *一般证明中可以取较粗糙的 C1, C2, n0，不用解出精确的点 f(n) = O(g(n)) 代表存在正常数 C, n0 使得 n ≥ n0 时 0 ≤ f(n) ≤ Cg(n)。 *即趋于无穷时 f 的阶不超过 g，g(n) = Θ(f(n)) 时必有 g(n) = O(f(n)) f(n) = Ω(g(n)) 代表存在正常数 C, n0 使得 n ≥ n0 时 0 ≤ Cg(n) ≤ f(n)。 *即趋于无穷时 g 的阶不超过 f，g(n) = Θ(f(n)) 时必有 g(n) = Ω(f(n)) f(n) = o(g(n)) 代表任意正常数 c 存在正常数 n0 使得 n ≥ n0 时 0 ≤ f(n) < cg(n)。 f(n) = ω(g(n)) 代表任意正常数 c 存在正常数 n0 使得 n ≥ n0 时 0 ≤ cg(n) < f(n)。 *大小写区别在存在与任意，也可以理解为大写剔除 Θ *实际使用时，O(f(n)) 可以代表某个满足 g(n) = O(f(n)) 的 g(n)，这样的匿名 [anonymous] 函数可 以正常参与运算，但不应出现存在歧义的情况 渐进关系的性质： *五种关系都具有传递性 *Θ, O, Ω 具有自反性 *Θ 与 Θ、O 与 Ω、o 与 ω 互相置换对称 **不是任何两个函数都渐进可比，例如 n 与 n 1+sin n，不存在 O 或 Ω 关系 上/下取整 取整性质：对正整数 a, b, n，⌈ ⌈n/a⌉ b ⌉ = ⌈ n ab ⌉, ⌊ ⌊n/a⌋ b ⌋ = ⌊ n ab ⌋ 引理：f(x) 是连续单调上升函数，且整点处才取整值，则 ⌈f(x)⌉ = ⌈f(⌈x⌉)⌉, ⌊f(x)⌋ = ⌊f(⌊x⌋)⌋ 引理证明：对第一个式子，若 ⌈f(x)⌉ ̸= ⌈f(⌈x⌉)⌉，由单调增可知 f(x) ≤ f(⌈x⌉)，从而 ⌈f(x)⌉ < ⌈f(⌈x⌉)⌉。 由向上取整定义可知 ⌈f(x)⌉ < f(⌈x⌉)，而 f(x) ≤ ⌈f(x)⌉，从而 ⌈f(x)⌉ 在 f(x) 与 f(⌈x⌉) 之间。由连 续定义知存在 x0 使得 f(x0) = ⌈f(x)⌉，由条件知 x0 必然为整数，但 x ≤ x0 ≤ ⌈x⌉，其由向上取整定 义只能为 ⌈x⌉，与 ⌈f(x)⌉ < ⌈f(⌈x⌉)⌉ 矛盾。另一个式子同理。 定理证明：取 f(x) = x b，x = n a 即可。 其他数学：模、指数、对数、阶乘 (Stirling 公式)、函数迭代 (f (n) (x)) *斐波那契 [Fibonacci] 数 a1 = a2 = 1, an = an−1 + an−2，通项为 √ 1 5 [(1+√ 5 2 )n − ( 1− √ 5 2 )n] *思考：服务器每隔 g 秒送包，拥有 k 个端口 (同时发 k 个)，收到的服务器需要花 L 秒时间解压，自 此每隔 g 秒给新服务器发送信息，时间与接受的服务器总数关系？(起初 1 对大兔子，大兔子每个隔 g 个月可生 k 对小兔子，小兔子需要 L 个月成熟，求第 n 个月的兔子对数？)[广义斐波那契数] 递归介绍 *递归可能分解为规模不等的子问题 求解递归方程的方法：替代法 (猜测上界后证明)、递归树法 (转化成树，结点表示不同层次产生的代价， 再采用边界求和)、主方法 (求解 T(n) = aT(n/b) + f(n)，a ≥ 1, b > 1，f(n) 是某给定函数 (并非对任 何都可解))