《算法基础》课程教学资源（学习笔记）算法基础课堂笔记.pdf_大学文库

算法基础笔记原生生物 *顾乃杰老师算法基础课堂笔记 [以 * 开头的行代表动机与注释等，** 开头的行代表补充内容] 目录一算法概念与数学基础 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)

二排序与顺序统计 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)⌉)

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

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