一算法概念与数学基础 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 <low to high if (sum 0) sum +=A[now] F (sum max now) i now <now max_now <sum if (sum <=e or now ==high) if (max now max) i max <-i now j_max <j_now max <max_now sum < else if(a[now】>) max_now <sum <-A[now] i_now <j_now <-i return (max,i_max,j_max) 51.4判断方法 替代法 包含两个步骤：猜测解的形式、归纳常数（直接替代）并证明解正确（要求易于猜得） 例：针对T(m)=2T(n/2)+n,先猜测解为Tm)=0(n1ogn),选取常数C>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 <‐ low to high if (sum > 0) sum += A[now] if (sum > max_now) j_now <‐ now max_now <‐ sum if (sum <= 0 or now == high) if (max_now > max) i_max <‐ i_now j_max <‐ j_now max <‐ max_now sum <‐ 0 else if (A[now] > 0) max_now <‐ sum <‐ A[now] i_now <‐ j_now <‐ i return (max,i_max,j_max) §1.4 判断方法 替代法 包含两个步骤：猜测解的形式、归纳常数 (直接替代) 并证明解正确 (要求易于猜得) 例：针对 T(n) = 2T(⌊n/2⌋) + n，先猜测解为 T(n) = O(n log n)，选取常数 C > 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 <-d+1 to n if (A[i]<A[i-d]) A[e]<-A[];ji-d; while (j>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 <‐ d+1 to n if (A[i]<A[i‐d]) A[0] <‐ A[i]; j <‐ i‐d; while (j>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.heap_size and A[l] > A[i] Largest = l else Largest = i if r <= A.heap_size and A[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