下载文档原格式
本周教学内容2选最大选第k 小 典型的分治算法选第二大 卷积及应用计算平面点集的凸包选最大与最小卷积计算 快速傅立叶 变换FFT 算法 选择问题 信号平滑处理 计算几何选最大与最小选择问题输入：集合L (含n个不等的实数)输出：L中第i 小元素i=1, 称为最小元素i=n，称为最大元素位置处在中间的元素，称为中位元素n为奇数，中位数唯一，i = (n+1)/2 n为偶数，可指定i = n/2+12选最大18 4 17 3 12算法：顺序比较1max k=1输出：max = 17，k =4算法最坏情况下的时间W (n )=n 1 38max k=217max k=4伪码算法Findmax输入：n 个数的数组L输出：max, k1. max ←L[1]2. for i ← 2 to n do3. if max < L[i]4. then max ←L[i]5. k ←i6. return max, k4选最大最小通常算法：1. 顺序比较，先选最大max2. 顺序比较，在剩余数组中选最小min，类似于选最大算法，但比较时保留较小的数时间复杂性：W(n) = n-1 + n-2 = 2n 35分组算法… …组1 组2 … 组 ⎣n /2⎦6大大大大小 小小小轮空伪码算法 FindMaxMin输入：n个数的数组L输出：max，min1．将n 个元素两两一组分成⎣n/2⎦组 2．每组比较，得到⎣n/2⎦个较小和⎣n/2⎦个较大3．在⎡n/2⎤个较大（含轮空元素）中找最大max4．在⎡n/2⎤个较小（含轮空元素）中找最小min7最坏情况时间复杂度行2 的组内比较：⎣n/2⎦次行3--4 求max和min比较：至多 2 ⎡n/2⎤-2次W(n) = ⎣n/2⎦ + 2 ⎡n/2⎤-2= n + ⎡n/2⎤-2= ⎡3n/2⎤-28分治算法1.将数组 L 从中间划分为两个子数组 L 1 和 L 29 4. max ← max{ max l , max 2}5. min ← min{ min l , min 2} 2. 递归地在 L 1中求最大 max l 和 min 13. 递归地在 L2中求最大 max 2 和 min 2最坏情况时间复杂度假设n = 2k，W(n) = 2W(n/2) + 2W(2) = 1解W(2k) = 2W(2k-1) + 2= 2[2W(2k-2) + 2]+ 2= 22W(2k-2) + 22+2 = …= 2k-1 + 2k-1 + … + 22 + 2= 3 2k-1 – 2 = 3n/2 - 210选择算法小结选最大：顺序比较, 比较次数n-1选最大最小•选最大+ 选最小, 比较次数2n-3 •分组：比较次数⎡3n/2⎤-2•分治：n=2k，比较次数 3n/2-211选第二大选第二大输入：n 个数的数组 L 输出：第二大的数 second 时间复杂度：W (n ) = n -1 + n -2 = 2n -3 通常算法：顺序比较1．顺序比较找到最大 max2．从剩下 n -1个数中找最大，就是第二大second2提高效率的途径•成为第二大数的条件：仅在与最大数的比较中被淘汰.•要确定第二大数，必须知道最大数. •在确定最大数的过程中记录下被最大数直接淘汰的元素.•在上述范围（被最大数直接淘汰的数）内的最大数就是第二大数.•设计思想：用空间换时间. 3锦标赛算法1.两两分组比较，大者进入下一轮，直到剩下 1个元素max为止2. 在每次比较中淘汰较小元素，将被淘汰元素记录在淘汰它的元素的链表上3. 检查max 的链表，从中找到最大元，即second4算法 FindSecond输入: n 个数的数组 L , 输出: second1．k ←n // 参与淘汰的元素数2．将k 个元素两两1组, 分成 ⎣k /2⎦ 组3．每组的2个数比较，找到较大数4．将被淘汰数记入较大数的链表5．if k 为奇数 then k ←⎣k /2⎦ +16．else k ←⎣k /2⎦ 7．if k >1 then goto 2 8．max ←最大数9．second ← max 的链表中的最大 伪码 5继续分组淘汰 一 轮 淘 汰实例 53 6 7 2 14 8 分组15 72 83 6 14 分组2 65 4 27 8分组3 4 2 7 6时间复杂度分析命题1 设参与比较的有t 个元素，经过i 轮淘汰后元素数至多为⎡t /2i⎤ .证对 i 归纳. i =1,分⎣t /2⎦组，淘汰⎣t /2⎦个元素，进入下一轮元素数是t -⎣t /2⎦ = ⎡t /2⎤假设i 轮分组淘汰后元素数至多为⎡t /2i⎤ ,那么i +1 轮分组淘汰后元素数为⎡⎡t /2i⎤ /2⎤ = ⎡t /2i+1⎤7时间复杂度分析（续）命题2 max 在第一阶段分组比较中总计进行了⎡log n⎤次比较.证假设到产生max 时总计进行k轮淘汰, 根据命题 1有⎡n/2k⎤ =1.若n=2d，那么有k = d = log n = ⎡log n⎤若 2d < n < 2d+1, 那么k = d + 1 = ⎡log n⎤8时间复杂度分析（续）第一阶段元素数：n比较次数: n -1淘汰了 n -1个元素时间复杂度是W (n ) = n -1 + ⎡log n ⎤ -1 = n + ⎡log n ⎤ -2. 第二阶段：元素数 ⎡log n ⎤ 比较次数: ⎡log n ⎤ -1 淘汰元素数为 ⎡log n ⎤ -1 9小结求第二大算法•调用2次找最大：2n-3•锦标赛算法：n + ⎡log n⎤-2 主要的技术：用空间换时间10一般选择问题的算法设计一般性选择问题问题：选第k 小.输入：数组S, S 的长度n, 正整数k, 1≤k≤n.输出：第k 小的数实例 1S={ 3,4,8,2,5,9,18 }，k = 4，解: 5实例 2统计数据的集合S，|S|=n，选中位数，k=⎡n/2⎤ 2一个应用：管道位置问题：某区域有n口油井，需要修建输油管道. 根据设计要求，水平方向有一条主管道，每口油井修一条垂直方向的支管道通向主管道. 如何选择主管道的位置，以使得支管道长度的总和最小？3……最优解:Y 坐标的中位数 … y ny 1y 2y n /2y n /2+1y 下移 ∆ k 个油井每条管线增加长度∆ 每条管线减少长度∆ 每条管线增加或减少至多∆ 4下移后支管线总长度增加简单的算法算法一：调用k次选最小算法时间复杂度为O (k n)算法二：先排序，然后输出第k 小的数时间复杂度为O(n log n)5分治算法假设元素彼此不等，设计思想：1. 用某个元素m*作为标准将S划分成S1与S2，其中S1的元素小于m*,S2的元素大于等于m*.2. 如果k≤ |S1|，则在S1中找第k小.如果k = |S1|+1，则m*是第k 小如果k > |S1|+1，则在S2中找第k-|S1| - 1小算法效率取决于子问题规模，如何通过m*控制子问题规模？6... ... 大小A : 数需要与m *比大小，B ：数大于m *C : 数小于m *,D :数需要与m *比大小m *的选择与划分过程 分组 1 2 ... ⎣n /5⎦ M m * 7实例：n=15, k=68 2 3 5 7 6 11 14 1 9 13 10 4 12 158 7 5 3 2 1411961151312104M m* = 98 7 5 3 2 1411961151312104C BAD 8, 7, 10, 4 需要与9比较88 7 5 3 2 1411961151312104S1 S28 7 5 3 2 6 1 4子问题子问题规模= 8，k=6归约为子问题9算法 Select (S, k )输入：数组 S ，正整数 k ， 输出：S 中的第 k 小元素1．将S 分5个一组, 共 n M = ⎡n /5⎤组 2．每组排序,中位数放到集合 M3．m *←Select(M ,⎡|M |/2⎤) //S 分A,B,C,D 4．A,D 元素小于m *放 S 1,大于m *放S 2 5．S 1 ← S 1⋃ C ; S 2 ← S 2⋃ B 6．if k = |S 1| + 1 then 输出 m * 7．else if k ≤ |S 1| 8． then Select (S 1, k )9. else Select (S 2, k －|S 1|－1)伪码10⇐ 递归计算子问题 划分小结选第k 小的算法：•分治策略•确定m*•用m*划分数组归约为子问题•递归实现11选择问题的算法分析算法 Select (S, k )1．将S 分5个一组, 共 n M = ⎡n /5⎤组 2．每组排序,中位数放到集合 M3．m *←Select(M ,⎡|M |/2⎤) //S 分A,B,C,D 4．A,D 元素小于m *放 S 1,大于m *放S 2 5．S 1 ← S 1⋃ C ; S 2 ← S 2⋃ B 6．if k = |S 1| + 1 then 输出 m * 7．else if k ≤ |S 1|8． then Select (S 1, k )9. else Select (S 2, k －|S 1|－1) 伪码2子问题规模至多： 2r +2r +3r +2 = 7r +2子问题规模估计n = 5 (2r +1), |A | = |D | = 2r用m *划分 3子问题规模估计不妨设 n = 5(2r +1)，|A |=|D |=2r ,划分后子问题规模至多为211021/5-=-=n n r 107231072)21107(27nn n r <-=+-=+ 4时间复杂度递推方程算法工作量W(n)行2: O(n) //每5个数找中位数,构成M 行3: W(n/5) // M 中找中位数m*行4: O(n) // 用m*划分集合S行8-9：W(7n/10) //递归W(n) W(n/5) + W(7n/10) + O(n)5递归树W (n )=W (n /5)+W (7n /10)+cncn 0.9cn 0.81cncn cn5 7cn 10 cn 25 7cn 50 7cn 50 49cn 100......W (n ) cn (1+0.9+0.92+...)=O (n )6讨论分组时为什么5个元素一组？3个一组或 7个一组行不行？分析：递归调用1. 求m*的工作量与 |M| = n/t相关，t 为每组元素数. t大, |M|小2. 归约后子问题大小与分组元素数t 有关 . t 大，子问题规模大73分组时的子问题规模假设t =3, 3个一组：r rn = 3(2r +1)r = (n/3 -1)/2 = n/6 -1/2子问题规模最多为 4r+1= 4n/6-18算法的时间复杂度算法的时间复杂度满足方程W(n) = W(n/3) + W(4n/6) + cn由递归树得W(n)= (n log n)关键：|M|与归约后子问题规模之和小于n，递归树每行的工作量构成公比小于 1 的等比级数，算法复杂度才是O(n).9小结选第k 小算法的时间分析•递推方程•分组时每组元素数的多少对时间复杂度的影响10卷积及其应用向量计算给定向量 a = (a 0, a 1, …, a n -1) b = (b 0, b 1, …, b n -1) 向量和 a +b = (a 0+b 0, a 1+b 1, …, a n -1+b n -1) 内积 a ⋅b = a 0b 0 + a 1b 1 + … + a n -1b n -1 卷积 a *b = (c 0, c 1, …, c 2n -2)，其中 22,...,1,0-==∑<=+n k b a c n i,j k j i ji k ， 2卷积的含义在下述矩阵中，每个斜线的项之和恰好是卷积中的各个分量a 0b a 1 b a n -1b ab 0 ab 1 ab n -2 ab n -1 3 a 0b 0 a 0b 1 a 0b n -2a 0b n -1 a 1b 0 a 1b 1a 1b n -2a 1b n -1 a n -1b 0 a n -1b 1 a n -1b n -2a n -1b n -1c 0 a n -2 b . . . a n -2b 0 a n -2b 1a n -2b n -2a n -2b n -1c 1 c n -1 c 2n -3 c 2n -2 . . . . . . . . .. . . . . . . . . . . . . . . . . .计算实例向量 a = (1, 2, 4, 3), b = (4, 2, 8, 0) ab 0 ab 1 ab 2 ab 3 a 0b 1 ⨯ 4 1 ⨯ 2 1 ⨯ 8 1 ⨯ 0 a 1b 2 ⨯ 4 2 ⨯ 2 2 ⨯ 8 2 ⨯ 0 a 2b 4 ⨯ 4 4 ⨯ 2 4 ⨯ 8 4 ⨯ 0 a 3b 3 ⨯ 4 3 ⨯ 2 3 ⨯ 8 3 ⨯ 0 4则 a +b = ( 5, 4, 12, 3 )a ⋅b = ( 4, 4, 32, 0 )a *b = (4, 10, 28, 36, 38, 24, 0 )c 2 = 4⨯4 + 2⨯2 +1⨯8 = 28卷积与多项式乘法 多项式乘法：C (x ) = A (x ) B (x ) A (x ) = a 0 + a 1x + a 2x 2 + … + a m -1x m -1 B (x ) = b 0 + b 1x + b 2x 2 + … + b n -1x n -1 C (x ) = a 0b 0 + (a 0b 1+a 1b 0) x + … + a m -1b n -1 x m+n -2 其中 x k 的系数2,...,1,0}1,...,1,0{}1,...,1,0{-+==∑-∈-∈=+n m k b a c n j m i k j i j i k， 5卷积应用：信号平滑处理由于噪音干扰，对信号需要平滑处理6。
第3章动态规划（Dynamic Programming）3.1 动态规划的设计思想313.2 动态规划的设计要素3.3 动态规划算法的典型应用投资问题背包问题最长公共子序列LCS图像压缩最大子段和最优二分检索树生物信息学中的动态规划算法3.1基本思想和使用条件例1求从始点到终点的最短路径S 1T 1B 16932u,2d,9d,115d,15S 2T 2A 1B 2C 1473644354d,3u,8u,5u,13S 3T 3A 2B 3C 24523273u,7d,6u,7d,10S 4T 4A 3B 4C 394141271u,1u,7d,5d,11S 5T 5A 4B 5C 43356u,4u,10动态规划的基本思想解：判断序列)}({min )(){min )(l l k k m l m l C F C B B F T C C F +==)}({min )(k k j kj lB F B A A F +=)}({min )(j j i ji A F A S S F += 任何最短路径的子路径都是优化函数的特点：任何最短路径的子路径都是相对于子路径始点和终点的最短路径求解步骤：确定子问题的边界、从最小的子问题开始进行多步判断:优化原则：一个最优决策序列的任何子序列本身一定是使用条件优化原则相对于子序列的初始和结束状态的最优的决策序列例2求总长模10的最小路径2222u,4u,25555u,6d,1ST最优解：下、下、下、下动态规划算法的解：下上上上动态规划算法的解：下、上、上、上不满足优化原则，不能使用动态规划设计技术3.2算法设计要素例3矩阵乘法：设A 1,A 2,…,A n 为矩阵序列，A i 为P i -1×P i 阶阵确乘法序使得乘的总矩阵，i = 1,2,…,n . 确定乘法顺序使得元素相乘的总次数最少. 输入：向量P = <P 0, P 1, … , P n >，n 个矩阵的行数、列数实例实例：P = <10, 100, 5, 50> A 1: 10 ×100,A 2: 100 ×5,A 3: 5 ×50,乘法次序:101005+10550=7500(A 1A 2)A 3: 10 ×100 ×5 + 10 ×5 ×50 7500 A 1(A 2A 3): 10 ×100 ×50 + 100 ×5 ×50 = 75000搜索空间的规模枚举算法：加⎟⎞⎜⎛n 21n 个括号的方法有种，是一个Catalan 数，是指数级别⎟⎠⎜⎝+n n 1)2(221)!2(12e n n n n W n Ω=Ω=π))(2)(21()!!1()(1en n e n n n n n n nn ++ππ)/2()21(23211222n e e n n nnn n nΩ=Ω=1222nn n n e n nn n +动态规划算法由i 和j 确定子问题的边界：输入P =< P 0, P 1, …, P n > , A i..j 表A 的结果其最后次相乘是示乘积A i A i+1…A j 的结果，其最后一次相乘是A i..j = A i..k A k+1..j 确定优化函数和递推方程：i j ]的最少的相乘次数则递推方程和初值m [i,j ] 表示得到A i..j 的最少的相乘次数，则递推方程和初值⎧=j i 0[⎪⎩⎪⎨<+++=−<≤ji P P P j k m k i m j i m j k i j k i }],1[],[{min ],1设立标记函数：为了确定加括号的次序，设计表s [i ,j ],记录求得最优时最后一次运算的位置算法1：递归实现算法1 RecurMatrixChain(P,i,j)1. m[i,j]←∞1i j2. s[i,j]←i3. for k←i to j 1 do3.for i to−1do4. q ←RecurMatrixChain(P,i,k)+ RecurMatrixChain(P,k+1,) + 1k(,,j)p i−1 p k p j5. if q<m[i,j]6. then m[i,j]←q7. s[i,j]←k8.Return m[i,j]这里没有写出算法的全部描述（递归调用的初值等）递归实现的复杂性复杂性满足递推关系⎧=∑−=⎪⎪⎨>+−+≥111))1()()((1)1()(n k n O k n T k T n O n T ∑∑∑−=−=−=+=−++≥⎩111)(2)()()()()(n n n k T n O k n T k T n O n T 111k k k 数学归纳法证明T (n )≥2n −1=2显然为真假设对于任何小于n k 命题为真n =2,显然为真. 假设对于任何小于n 的k 命题为真,则11122)()(2)()(−−−+≥+≥∑∑n k n n O k T n O n T 11112)12(2)(−−==≥−+=n n k k n O子问题重复计算n=5，计算子问题：81个；不同的子问题：15个子问题1‐12‐23‐34‐45‐51‐22‐33‐44‐51‐32‐43‐51‐42‐51‐5数8121412845542221112算法2：迭代实现算法2 MatrixChain(P,n)[,j]1．令所有的m i初值为02．for r ←2 to n do// r为计算的矩阵链长度3．for i←1 to n−r+1 do //n-r+1为最后r链的始位置4．j ←i+r−1// 计算链i—jj//j5．m[i,j] ←m[i+1,j] + p i−1*p i*p j// A i(A i+1..A j)6. s[i,j] ←i//记录分割位置6]7. for k ←i+1 to j−1 do[][j]p i1p k p j(i k)(k+1j)8. t ←m i,k]+m k+1,]+ −**//(A..A A..A9. if t<m[i,j]10. then m[i,j]←t11k11. s[i,j]←k复杂性：行2,3,7都是O(n)，循环内为O(1),W(n)=O(n3)n=8的迭代过程A1 A2A3A4A5A6 A7A8r=2r3=3r=4r=5r=66r=7r=812实例输入P = <30, 35, 15, 5, 10, 20>, n =5，矩阵链：A A A A A ，其中12345A 1:30×35，A 2:35×15，A 3:15×5，A 4:5×10，A 5:10×20r =1m [1,1]=0m [2,2]=0m [3,3]=0m [4,4]=0m [5,5]=0r =2m [1,2]=15750m [2,3]=2625m [3,4]=750m [4,5]=1000备忘录[][][][]r =3m [1,3]=7875m [2,4]=4375m [3,5]=2500r =4m [1,4]=9375m [2,5]=71251118r =5m [1,5]=11875r =2s [1,2]=1s [2,3]=2s [3,4]=3s [4,5]=4r =3s [1,3]=1s [2,4]=3s [3,5]=3r =4s [1,4]=3s [2,5]=3r =5s [1,5]=3[,]解: (A 1(A 2A 3))(A 4A 5)两种实现的比较递归算法：时间复杂性高，空间较小非递归算法：时间复杂性较低，空间消耗多时间复杂性不同的原因：递归动态规划算法的子问题被多次重复计算，子问题计算次数呈指数增长迭代动态规划算法每个子问题只计算一次，时间复杂度等于备忘录中各项的计算量之和对于需要追踪解的问题要备忘录中各项的计算量之和（对于需要追踪解的问题，还要加上追踪工作量，一般不超过备忘录计算工作量），通常是问题规模的多项式函数迭代动态规划算法提高效率的原因：以空间换时间小结(1)划分子问题用参数表达子问题的边界，将问题求解转变成多步判断用参数表达子问题的边界将问题求解转的过程.(2)确定优化函数以该函数的极大(或极小)作为判断的依据，确定是否满足优化原则.(3) 列出关于优化函数的递推方程(或不等式)和边界条件(4) 自底向上计算，以备忘录方法(表格)存储中间结果(5) 考虑是否需要设立标记函数(5)3.3.1 投资问题m 元钱，n 项投资，f i (x): 将x 元投入第i 项项目的效益目标函数max {f1(x1) f2(x2) … f n(x n) }max{)+)+…+)}+ x2+ … + x n= m，x i∈N约束条件x1实例：5万元钱，4个项目，效益函数如下表所示x f1(x)f2(x)f3(x)f4(x)00000111022021251021313103022414153223515204024子问题划分和优化函数设F k (x ) 表示x 元钱投给前k 个项目的最大效益多步判断假设知道p 元钱（p ≤x ）投给前k −1个项目的最大效益决定钱投给前个的案益，决定x 元钱投给前k 个项目的分配方案递推方程和边界条件1)}()({max )(10k x x F x f x F k k k k xx k k >−+=−≤≤)()(11x f x F =实例的计算))))x F 1(x ) x 1(x )F 2(x ) x 2(x )F 3(x ) x 3(x )F 4(x ) x 4(x )111 111 011 020 1122120131311212 212 013 131 1313 316 230 333 114421341301414 421 341 350 1515 526 443 461 1解x 1=1, x 2=0, x 3=3, x 4=1 F 4(5) = 61算法的复杂度分析表中有m 行n 列, 共计mn 项1)}()({max )(10k x x F x f x F k k k k xx k k >−+=−≤≤对第F k (x )项(2≤k ≤n ,1≤x ≤m ) 需要x +1次加法,x 次比较)()(11x f x F =)3()1(21)1(m m n x n m+−=+∑∑加法次数)1()1(121m m n x n mk x +−=∑∑==比较次数)()(2221nm O n W k x ===3.3.2背包问题(K k P bl )一个旅行者准备随身携带一个背包.(Knapsack Problem)个旅行者准备随身携带个背包. 可以放入背包的物品有n 种, 每种物品的重量和价值分别为w j , v j .如果背包的最大重量限制是b , 怎样选择放入背包的物品以使得背包的价值最大?∑nmax1=nj jjx v目标函数N,1∈≤∑=j j j j x b x w 约束条件线性规划问题由线性条件约束的线性函数取最大或最小的问题整数规划问题线性规划问题的变量x 都是非负整数j子问题划分、优化函数、标记函数F k (y )：装前k 种物品,总重不超过y, 背包的最大价值i k ：装前k 总重不超过y, 背包达最大价值时(,y )装前种物品,总不超y,背最大价值时装入物品的最大标号递推方程边界条件标记函数递推方程、边界条件、标记函数})(),(max{)(1+−=−v w y F y F y F k k k k k 0,0)0(,0,0)(0⎥⎢≤≤=≤≤=y n k F b y y F k 0)(111<−∞=⎥⎦⎢⎣=F v w y F )(y y k ⎨⎧−+−>=−−kk k k k k V W y F y F y i y i )()()()(11⎩+≤−k k k k V W y F y F k)()(1实例计算v1= 1, v2= 3, v3= 5, v4= 9,= 2, w2= 3, w3= 4, w4= 7,w=2=3=4=71b= 10F k(y) 的计算表如下:)yk 12345678910 10112233445 20133466799 30135568101011 40135569101012追踪问题的解k y12345678910 10111111111 20122222222 30123333333 40123334344在上例中, 求得i4(10)=4 ⇒x4≥1i(10－w)=i(3)=2 ⇒x≥1，x=1, x=0444243i2(3－w2)=i2(0)=0 ⇒x2= 1，x1=00, x21, x30, x41=0,=1,=0,=1解x1追踪解x的算法j算法TrackSolution(y),,,y,,,输入：i表，其中k=1,2,…,n，=1,2,…,bk, x2, … , x n，n种物品的装入量输出：x11. for j←1 to n do2. x j ←03. y ←b, j←n4. j ←i j(y)，5. x j ←16. y ←y−w j7. while i j(y)=j do8. y ←y−w j9. x j ←x j+110. if i j(y) ≠0 goto 410if)0goto43.3.3最长公共子序列LCS相关概念X 的子序列Z ：设序列X , Z ,>=<>=<m z z z Z x x x X ...,...,,21若存在X 的元素构成的严格递增序列Z X k ,,,21><k i i i x x x ,...,,21使得，则称Z 是X 的子序列X 与Y 的公共子序列Z ：Z 是X 和Y 的子序列k j x z j i j ,...,2,1,==子序列的长度：子序列的元素个数问题描述, x2, … , x m>, Y=<y1, y2, … , y n>给定序列X=<x1求X 和Y的最长公共子序列X实例X: A B C B D A BY:B D C A B A最长公共子序列: B C B A蛮力算法：检查X的每个子序列在Y中出现()每个子序列O n) 时间，X 有2m 个子序列，最坏情况下时间复杂度：O(n2m)子问题划分及依赖关系子问题边界：X和Y 起始位置为1，X的终止位置是i，Y 的终止位置是j，记作记作X i=<x1,x2,…,x i>，Y j=<y1,y2,…,y j>依赖关系：X<x1,x2,…,x m>, Y<y1,y2,…,y n>, Z<z1,z2,…,z k>，=<>=<>=<Z 为X 和Y 的LCS，那么=y n⇒z k=x m=y n,且Z k−1是X m−1与Y n−1的LCS；(1) 若xm(2) 若x m≠y n, z k≠x m⇒Z是X m−1与Y 的LCS；(3) 若x m≠y n, z k≠y n⇒Z是X与Y n−1的LCS.满足优化原则和子问题重叠性递推方程、标记函数令X 与Y 的子序列<<>X i = <x 1, x 2, … , x i >，Y j = <y 1, y 2, … , y j > C [i ,j ]：X i 与Y j 的LCS 的长度j 递推方程⎧==若⎪⎨=>+−−=ji y x j i j i C j i j i C ],0,1]1,1[000],[若或标记函数：B i, j ], 其值为字符↖、←、↑，分别表示C i,j ⎪⎩≠>−−j i y x j i j i C j i C ,0,]},1[],1,[max{若[j ][j ]取得最大值时的三种情况动态规划算法算法3.4LCS(X,Y,m,n)1. for i←1 to m do//行1-4边界情况2. C[i,0]←03. for i←1 to n do4. C[0,i]←04[05. for i←1 to m doj6．for ←1 to n do7. if X[i]=Y[j]8. then C[i,j]←C[i−1,j−1]+19. B[i,j]←’É’10. else if C[i−1,j] ≥C[i,j−1]11. then C[i,j]←C[i−1,j]11then i j112. B[i,j]←’↑’[,j][,j]13. else C i,j←C[i−1]14. B[i,j]←’←’利用标记函数构造解算法Structure Sequence(B, i, j)输[,j]输入：B i输出：X与Y的最长公共子序列1. if i=0 or j=0 then return //一个序列为空2. if B[i,j] =“↖”“”3. then 输出X[i]4. Structure Sequence(B, i1, j1)4Structure Sequence(B i－j－1)5. else if B[i,j]=“↑”then Structure Sequence (B, i－1, j)q(,,j)6. else Structure Sequence (B, i, －1)算法的计算复杂度计算优化函数和标记函数：时间为O(mn)构造解：每一步至少缩小X 或Y 的长度，时间Θ(m+n）空间：Θ(mn))实例输入：X =<A,B,C,B,D,A,B>, Y =<B,D,C,A,B,A>，标记函数：1234561B [1,1]= ↑B [1,2]= ↑B [1,3]= ↑B [1,4]=↖B [1,5]= ←B [1,6]=↖2B [2,1]=↖B [2,2]= ←B [2,3]= ←B [2,4]= ↑B [2,5]=↖B [2,6]= ←3B [3,1]= ↑B [3,2]= ↑B [3,3]=↖B [3,4]= ←B [3,5]= ↑B [3,6]= ↑4B [4,1]= ↑B [4,2]= ↑B [4,3]= ↑B [4,4]= ↑B [4,5]=↖B [4,6]= ←5B [5,1]= ↑B [5,2]= ↑B [5,3]= ↑B [5,4]= ↑B [5,5]= ↑B [5,6]= ↑6B [6,1]= ↑B [6,2]= ↑B [6,3]= ↑B [6,4]=↖B [6,5]= ↑B [6,6]=↖[71][72][73][74][75][76]解：X [2],X [3], X [4], X [6], 即B, C, B, A7B [7,1]= ↑B [7,2]= ↑B [7,3]= ↑B [7,4]= ↑B [7,5]= ↑B [7,6]= ↑3.3.4图像压缩像素点灰度值:0∼255，表示为8位二进制数:{,,…,像素点灰度值序列: { p 1, p 2,…, p n }，p i 为第i 个像素点灰度值变位压缩存储格式: 将{ p 1, p 2,…, p n }分割m 段S 1, S 2, … ,S m i l i 个像素，每个像素b i , h 段最大像素的位数段有[]个像素每个像素[]位,i 为该段最大像素位数⎤⎡+=≤≤∈)1max log(,8][k Si i p h i b h ⎥⎢p ik约束条件：每段像素个数l [i ] ≤256(3)+段头11位：b [i ]的二进制表示(3 位) + l [i ]的二进制表示(8位)i 段占用空间：b [i ]×l [i ] + 11给定像素序列{确定最优分段即问题：给定像素序列{ p 1, p 2, …, p n }，确定最优分段，即为分段},...,,{)},11][][({min jS S S T i l i b =+×211j i T∑=实例灰度值序列P={10,12,15,255,1,2,1,1,2,2,1,1}={10,12,15}，S2={255}, S3={1,2,1,1,2,2,1,1}分法1：S1分法1{,,,,,,,,,,,}2：S={10,12,15,255,1,2,1,1,2,2,1,1}分法3：分成12组，每组一个数存储空间分法1：11×3+4×3+8×1+2×8=69分法2：11×1+8×12=1071812107分法3：11×12+4×3+8×1+1×5+2×3=163结论：分法1是其中最优的分法算法设计递推方程设s [i ]是像素序列{p 1, p 2, … , p i }的最优分段所需存储位数−−=*⎤⎡=+++≤≤11)},1max(][{min ][}256,min{1i k i k i b k k i s i s ⎥⎥⎢⎢+≤≤)1}{max log(),max(k j k i p j i b P 1P 2… P i-k P i-k +1 … P ik*b max(i -k +1,i )位S [i-k ]位k 个灰度算法Compress (P,n)//计算最小位数S[n]1.Lmax←256; header←11; S[0]←0//最大段长Lmax, 头header2. for i←1 to n do3. b[i]←length(P[i]) //b[i]是第i个灰度P[i]的二进制位数4. bmax←b[i] //3-6行分法的最后一段只有P[i]自己4b]//36行分法的最后段只有5. S[i]←S[i−1]+bmax6.6. l[i]←17. for j←2 to min{i,Lmax} do//最后段含j 个像素8. if bmax<b[i−j+1] //统一段内表示像素的二进制位数9. then bmax←b[i−j+1]10. if S[i]>S[i−j]+j*bmax11. then S[i]←S[i−j]+j*bmax11th b12. l[i]←j13. S[i]←S[i]header 时间复杂度T(n)O(n) 13.]+header)=P = <10, 12, 15, 255, 1, 2>.S [1]=15, S [2]=19, S [3]=23, S [4]=42, S [5]=50[1]1[2]2[3]3[4]1[5]2实l [1]=1, l [2]=2, l [3]=3,l [4]=1, l [5]=2 例10121525512S [5]=501×2＋1110121525512S [4]=422×2＋1110121525512S [3]=233×8＋1110121525512[2]19S [2]=19 4×8＋1110121525512[1]=15S [1]=15 5×8＋11101215255126×8＋11追踪解算法Traceback(n,l)输入：数组l输入数组l输出：数组C// C[j]是从后向前追踪的第j段的长度1. j←1 // j为正在追踪的段数11//2. while n≠0 do3]3. C[j]←l[n]4. n←n－l[n]5. j←j+15+1n时间复杂度：O()3.3.5最大子段和问题：给定n 个整数（可以为负数）的序列)∑j(a 1, a 2, … , a n ) =≤≤≤ik knj i a}max,0max{1实例(21141352)求实例：(-2, 11, -4, 13, -5, -2)解：最大子段和a 2+a 3+a 4= 20 算法1---顺序求和+比较2算法2---分治策略算法3---动态规划算法1顺序求和+比较算法Enumerate输入：数组A[1..n]输出：sum, first, last输出1. sum←02. for i←1 to n do //i为当前和的首位置2for1to do//3. for j←i to n do// j为当前和的末位置为[]到[j]之和4. thissum←0 // thissum A i A5. for k←i to j do6. thissum←thissum+A[k]7. if thissum>sum8. then sum←thissum9. first←i// 记录最大和的首位置9//10．last←j // 记录最大和的末位置时间复杂度：O(n3)复杂度算法2 分治策略将序列分成左右两半，中间分点center递归计算左段最大子段和leftsuml ft递归计算右段最大子段和rightsuma center→a1的最大和S1, a center+1→a n的最大和S2max { leftsum, rightsum, S1+S2}S1+S2leftsum rightsumA[1] … A[k] A[k+1] … A[n]分治算法算法MaxSubSum(A, left, right）f g输入：数组A，left，right分别是A的左、右边界输出：A的最大子段和sum及其子段的前后边界1．if |A|=1 then 输出元素值（当值为负时输出0）2．center←⎣(left+right)/2⎦⎣3．leftsum←MaxSubSum(A,left,center) //子问题A1 4．righsum←MaxSubSum(A,center+1,right) //子问题A 2i h Ma S bS m(t+1i ht)//5．S1←A1[center] //从center向左的最大和6．S2←A2[center1] //从center1向右的最大和+1]//+17．sum←S1+S28．if leftsum> sum then sum←leftsum9．if rightsum>sum then sum←rightsumT(n)2T(n/2)O(n), T(c)O(1)时间：)=2/2)+),)=(1)T(n)=O(n log n)算法3：动态规划令C [i ]是A [1..i ]中必须包含元素A [i ]的最大子段和i}][{max ][1∑=≤≤=kj ik j A i C A [1] A [2] A [3] … A [j -1] A [j ] … A [n ]最大子段和C [j -1]最大子段和C [j ]递推方程: C [i ]= max{C [i －1]+A [i ], A [i ] } i =2，…,n[1][1]>0[1]=0C [1]=A [1] 若A [1]>0, 否则C [1]=0 解：]}[{max )(OPT i C A =1ni ≤≤算法MaxSum 算法3.10 MaxSum(A,n)输入：数组A输出：最大子段和sum, 子段的最后位置c 输出最大子段和1. sum←02．b←0 // b是前个最大子段和0//是前一个最大子段和3. for i←1 to n do4. if b>05. then b←b+A[i]6. else b←A[i]7. if b>sumif8. then sum←b9. c←i //记录最大和的末项标号9i10. return sum，c时间复杂度：O(n), 空间复杂度：O(n)时间复杂度)空间复杂度3.3.6最优二叉检索树设集合S 为排序的n 个元素x 1<x 2<…<x n ，将这些元素存储在一棵二叉树的结点上以查找x 储在棵二叉树的结点上，以查找x 是否在这些数中. 如果x 不在，确定x 在那个空隙.检索方法：1.初始，x 与根元素比较；4262.x <根元素，递归进入左子树；3.x >根元素，递归进入右子树；根元素算法停止输出531L 64.x =根元素，算法停止，输出x ；5.x 到达叶结点，算法停止，输L 0L 1L 2L 4L 5L 3S ={ 1, 2, 3, 4, 5, 6}出x 不在数组中.存取概率不等情况空隙：(-∞, x), (x1, x2), … , (x n−1, x n), (x n,+∞) ,1x 0= -∞, x n+1=∞, x2, …, x n>,给定序列S = <x1x 在x i 的概率为b i , x 在(x i , x i+1) 的概率为a i ,S的存取概率分布如下：P = <a0, b1, a1, b2, a2, … , b n, a n>实例S={1,2,3,4,5,6}P=<0.04,0.1,0.01,0.2,0.05,0.2,0.02,0.1,0.02,0.1,0.07, 0.05,0.04> 0040100102005020020100201007005004实例S ={123456}4T 1S = { 1, 2, 3, 4, 5, 6 }P = < 0.04, 0.1, 0.01, 0.2, 0.05, 0.2,0020100201007005260.02, 0.1, 0.02, 0.1, 0.07, 0.05，0.04 >531L 6L 0L 1L 2L 4L 5L 3m (T 1)=[1*0.1+2*(0.2+0.05)+3*(0.1+0.2+0.1)]+[3*(0.04+0.01+0.05+0.02+0.02+0.07)+2*0.04]= 1.8+0.71=2.51实例S = { 1, 2, 3, 4, 5, 6 }P 00401001020050221L 0T 2P = < 0.04, 0.1, 0.01, 0.2, 0.05, 0.2,0.02, 0.1, 0.02, 0.1, 0.07, 0.05，)[1*01+2*02+3*014L 10.04 >m (T 2) =[ 1*0.1+2*0.2 + 3*0.1+ 4*(0.2+0.05) + 5*0.1 ]+[1*004+2*00163+ [ 1*0.04 + 2*0.01+ 4*(0.05 + 0.02 + 0.04)5*(002007)]5L 2L L L 6L 3+ 5*(0.02 + 0.07)]= 2.3 + 0.95 = 3.2545问题数据集S ＝<x 1,x 2,…,x n >存取概率分布P =<a 0, b 1, a 1, b 2, … , a i , b i +1, …, b n , a n >结点x i 在T 中的深度是d (x i ), i =1,2,…,n ，空隙L j 的深度为d(L j ), j =0,1,…,n ，平均比较次数为：∑∑++=nnjjiiLd a x d b t )())(1(问题：给定数据集S 和相关存取概率分布P ，求一棵最优的==i j 1(即平均比较次数最少的)二分检索树.算法设计:子问题划分S[i,j] = <x i, x i+1, … , x j> 是S 以i 和j 作为边界的子数据集[,j]i1,i,i,i+1,,j,j是对应[,j]存取概率分布P i] = <a－b a, b, … , b, a>S i例:S=<A,B,C,D,E>,,,,,,,,,, P=<0.04, 0.1, 0.02, 0.3, 0.02, 0.1, 0.05, 0.2, 0.06, 0.1, 0.01> S[2,4]=<B, C, D>P[2,4]=<0.02, 0.3, 0.02, 0.1, 0.05, 0.2, 0.06>子问题划分：以x作为根，划分成两个子问题：kS[i,k−1], P[i,k−1]S[k+1,j], P[k+1,j]例:以B为根，划分成以下子问题：S[1,1]=<A>，P[1,1]=<0.04, 0.1, 0.02>S[3,5]=<C,D,E>, P[3,5]=<0.02, 0.1, 0.05, 0.2, 0.06,0.1,0.01>递推方程设m [i,j ] 是相对于输入S [i ,j ] 和P [i ,j ] 的最优二叉搜索树的平均比较次数，令∑∑+=jqjpba j i w ],[是P [i ,j ] 中所有概率（包括数据元素与空隙）之和=−=iq i p 1递推方程：]}ni i i m nj i j i w j k m k i m j i m jk i ,...,21011]},,[],1[]1,[{min ],[==−≤≤≤+++−=≤≤,,,,],[。
第6章算法分析与问题的计算复杂度6.1 平凡下界6.2 直接计数求解该问题所需要的最少运算6.26.3 决策树6.4 检索算法的时间复杂度分析6.5 排序算法的时间复杂度分析656.6 选择算法的时间复杂度分析算法正确性•正确性在给定有效输入后, 算法经过有限时间的计算并产生正确的答案, 就称算法是正确的.•正确性证明的内容：–方法的正确性证明——算法思路的正确性. 证明一系列与算法的工作对象有关的引理、定理以系列与算法的工作对象有关的引理定理以及公式.–程序的正确性证明——证明所给出的一系列指证明所给出的系列指令确实做了所要求的工作.2工作量‐‐时间复杂性分析计量工作量的标准: 对于给定问题,该算法所执行的基本运算的次数.的基本运算的次数基本运算的选择：根据问题选择适当的基本运算问题基本运算在表中查找x比较实矩阵相乘实数乘法排序比较较遍历二叉树置指针两种时间复杂性:最坏情况下的复杂性W(n)平均情况下的复杂性A(n)3占用空间‐‐空间复杂性分析•两种占用–存储程序和输入数据的空间–存储中间结果或操作单元所占用空间‐‐额外空间•影响空间的主要因素：–存储程序的空间一般是常数(和输入规模无关)–输入数据空间为输入规模O(n)–空间复杂性考虑的是额外空间的大小额外空间相对于输入规模是常数•, 称为原地工作的算法.•两种空间复杂性:–最坏情况下的复杂性–平均情况下的复杂性.4简单性•含义：算法简单，程序结构简单.•好处：容易验证正确性便于程序调试•简单的算法效率不一定高. 要在保证一定效率的前提下力求得到简单的算法5基于时间的最优性•含义：指求解某问题算法类中效率最高的算法•两种最优性最坏情况下最优：设A 是解某个问题的算法, 如果在解这,个问题的算法类中没有其它算法在最坏情况下的时间复杂性比A 在最坏情况下的时间复杂性低, 则称A 是解这个问题在最坏情况下的最优算法.平均情况下最优：设A 是解某个问题的算法, 如果在解这个问题的算法类中没有其它算法在平均情况下的时间复杂性比A 在平均情况下的时间复杂性低, 则称A 是解这个问题在平均情况下的最优算法6寻找最优算法的途径(1) 设计算法A, 求W(n)，得到算法类最坏情况下时间复杂度的一个上界(2) 寻找函数F n使得对任何算法都存在一个规模为n 的输()(),入并且该算法在这个输入下至少要做F(n)次基本运算，得到该算类最坏情况时复杂度个界到该算法类最坏情况下时间复杂度的一个下界(3) 如果W(n)=F(n)或W(n)=Θ(F(n)), 则A是最优的.(4) 如果W(n)>F(n), A不是最优的或者F(n)的下界过低. (4))改进A或设计新算法A’使得W’(n)<W(n).重新证明新下界F’(n)使得F’(n)>F(n).,()()()(())重复以上两步, 最终得到W’(n) = F’(n) 或者W’(n) = ΘF’(n76.1 平凡下界算法的输入规模和输出规模是它的平凡下界例1问题：写出所有的n阶置换求解的时间复杂度下界为Ω(n!)例2问题：求n次实系数多项式多项式在给定x的值求解的时间复杂度下界为Ω(n)例3问题：求两个n×n 矩阵的乘积求解的时间复杂度下界是Ω(n2)6.2 直接计数最少运算数例4找最大算法Findmax输入数组L, 项数n≥1输出L中的最大项MAX1.1. MAX←L(1);i←2;2. while i≤n do3. if MAX<L(i) then MAX←L(i);3if)then4. i←i+1;W(n)=n-1以比较作为基本运算的算法类的上界：n1-1找最大问题的复杂度下界：在n 个数的数组中找最大的数, 以比较做基本运算的算法类中的任何算法在最坏情况下至少要做n－1 次比较.因为MAX是唯一的, 其它的n－1 个数必须在比较后被淘证是唯的1汰. 一次比较至多淘汰一个数, 所以至少需要n－1 次比较.结论: F indmax 算法是最优算法.106.3决策树（Decision Tree）二叉树的性质叉树的性质命题1 在二叉树的t 层至多2t 个结点命题2 深度为d 的二叉树至多2d+1-1 个结点.命题3 n个结点的二叉树的深度至少为⎣log n⎦.3l命题4 设t 为二叉树的树叶个数，d为树深，如果树的每个内结点都有2个儿子，则t≤2d.116.4 检索算法时间复杂度分析检索问题: 给定按递增顺序排列的数组L (项数n ≥1)和数x ，L 0算法1 如果x 在L 中, 输出x 的下标; 否则输出0. 顺序捡索输入: L , x 输出: j 1. j ←12. while j ≤n and L (j )≠x do j ←j +1 3if then3. if j >n then j ←0分析：设x 在L 中每个位置和空隙的概率都是1/(2n +1) W (n )=nA (n )=[(1+2+...+n )+n (n +1)]/(2n +1)≈3n /4.12二分捡索最坏时间复杂度定理1 W (n ) = ⎣log n ⎦+ 1 n ≥1证对n 归纳n =1时, 左= W (1)=1, 右= ⎣log 1⎦+1 = 1. n 假设对一切k , 1≤k <n , 命题为真, 则⎣⎦⎣⎦⎣⎦1log 1)(1)(22++=+=W n W n ⎣⎦1log ⎨⎧−+=n n 为偶数⎣⎦⎣⎦1log 1)1log(+=⎩+n n n 为奇数13二分捡索的平均时间复杂度令n =2k －1, S t 是算法做t 次比较的输入个数, 1≤t ≤k 则S 1=1=20, S 2=2=21, S 3=22, S 4=23, ... , S t = 2t −1, t <k S k = 2k −1 + n + 1其中2k −1 为x 在表中做k 次比较的输入个数1)...21(12)(21k kS S S n n A ++++=14求和1+=1)...21(12)(121+++−kS S S n n A k t k 1)]1(2[121++∑+==n k t n t )]1(12)1[(12−+++−+=n k k n k⎣⎦21log 21221+=−=+≈n k k k 15捡索问题的决策树设A是一个捡索算法, 对于给定输入规模n, A的一棵决策树是一棵二叉树, 其结点被标记为1, 2, ... , n, 且标记规则是: 棵二叉树12•根据算法A，首先与x 比较的L 的项的下标标记为树根.•假设某结点被标记为i,–i 的左儿子是：当x<L(i)时，算法A下一步与x比较的项的下标–i 的右儿子是：当x>L(i)时，算法A下一步与x比较的项的下标–若x<L(i) 时算法A 停止, 则i 没有左儿子.–若x>L(i) 时算法A 停止, 则i 没有右儿子.16实例改进顺序捡索算法和二分捡索算法的决策树，n =1512841231426101415135********给定输入, 算法A 将从根开始, 沿一条路径前进, 直到某.个结点为止. 所执行的基本运算次数是这条路径的结点个数. 最坏情况下的基本运算次数是树的深度+1.17检索问题的复杂度分析定理对于任何一个搜索算法存在某个规模为n 的输入使得该算法至少要做⎣log n⎦+1 次比较.证由命题3, n 个结点的决策树的深度d 至少为⎣log n⎦, 故3n dW(n)=d+1 = ⎣log n⎦+1.结论: 对于有序表搜索问题, 在以比较作为基本运算的算法类中, 二分法在最坏情况下是最优的.186.5 排序算法时间复杂度分析•冒泡排序•快速排序与二分归并排序•堆排序序算界•排序算法的复杂度下界19冒泡排序输入: L, n≥1.输出: 按非递减顺序排序的L.:算法bubbleSort1n//1. FLAG←n //标记被交换的最后元素位置2. while FLAG> 1 do3. k←FLAG13.−4. FLAG ←1j5. for =1 to k do6. if L(j) > L(j+1) then do7. L(j) ↔L(j+1)8. FLAG←j20实例5 3 26 9 1 4 8 73 2 5 6 14 8 7923 5 1 4 6 78 92 531467892 1345678 91 2 3 4 5 6 7 8 9特点交换发生在相邻素之间特点：交换发生在相邻元素之间21置换与逆序•逆序令L ={1,2,...,n }, 排序的任何输入为L 上的置换. 在置j )为该置换的个逆序换a 1a 2...a n 中若i <j 但a i >a j , 则称(a i ,a j ) 为该置换的一个逆序. 序序个•逆序序列在i 右边，并且小于i 的元素个数记作b i , i =1, 2,…,n . ( b 1, b 2, …, b n ) 称为置换的逆序序列•实例置换 3 1 6 5 8 7 2 4逆序序列为(0, 0, 2, 0, 2, 3, 2, 3)22序序列的性质逆序序列的性质•b1=0; b2=0,1; … ; b n= 0,1, … , n-1•总共n!个不同的逆序序列置换与它的逆序序列构成一一对应•逆序数：置换中的逆序总数b+ b+ … +b12n•实例置换 3 1 6 5 8 7 2 4逆序序列为( 0, 0, 2, 0, 2, 3, 2, 3 )逆序数1223冒泡排序算法复杂度分析•最坏情况分析：W(n)=O(n2), 至多巡回O(n)次，每次O(n).•对换只发生在相邻元素之间，每次相邻元素交换只消除1个逆序，比较次数不少于逆序数，最大逆序数n(n−1)/2，于是W(n)=Θ(n2).•平均情况：设各种输入是等可能的，置换α的逆序序列是(b1, b2, … , b n), 置换α′的逆序序列为(0−b1, 1−b2, … ,n−1−b，αα′的逆序数之和为n n−1)/2. n!个置换分成)与的逆序数和为()个换分成nn!/2个组，每组逆序之和为n(n−1)/2.平均逆序数()/，平均的交换次数为()/.n n−1)/4n n−1)/4.•冒泡排序的最坏和平均复杂性均为Θ(n2)24快速排序与二分归并排序•快速排序最坏情况O(n2)平均情况O(n log n))•二分归并排序最坏情况O(n log n)平均情况O(n log n))25堆排序•堆的定义•堆的运算–堆整理Heapify(A,i)H if(–复杂度分析–建堆Build-Heap(A)–复杂度分析•堆排序算法Heap-sort(A)–复杂度分析26堆的定义设T 是一棵深度为d 的二叉树，结点为L中的元素.若满足以下条件，称作堆.若满足以下条件称作(1) 所有内结点（可能一点除外）的度数为2(2) 所有树叶至多在相邻的两层所有树叶多在相邻的(3) d−1 层的所有树叶在内结点的右边(4) d−1 层最右边的内结点可能度数为1（没有右儿子）(5) 每个结点的元素不小于儿子的元素若只满足前(4)条，不满足第(5)条，称作堆结构27实例116141023793 845678910堆存储在数组A241A[i]：结点i 的元素，例如A[2]=14.left(i), right(i) 分别表示i 的左儿子和右儿子28堆的运算：整理算法Heapify(A,i)1. l ←left(i)1l l f2. r←right(i)3if]and]>]3. if l≤heap-size[A] and A[l] > A[i]4. then largest←lg5. else largest←i6. if r ≤heap-size[A] and A[r] > A[largest]7. then largest ←r8. if largest≠i8if l i9. then exchange A[i] ↔A[largest]10. Heapify(A, largest)10Heapify(29Heapify 实例p y 1641012316141012379314456797934456792818102818102)161410123Heapify(A ,2)79324184567891030(1)复杂度分析每次调用为O(1)子堆大小至多为原来的2/3递推不等式T(n) ≤T(2n/3) + Θ(1)解得T(n) = Θ(log n)或者T(h) = Θ(h) xh为堆的根的高度结点总数+1)/21(3（距树叶最大距离）x+(x-1)/2+1=(3x+1)/231堆的运算：建堆Build-Heap(A)算法Build Heap(1．heap-size[A] ←length[A]2．for i ←⎣length[A]/2⎦downto 13．do Heapify(A, i)do Heapify()32414113169102234567131691022345671487891041411487891013234567110169314234567实169102871489102878910例41161231610793142345671410793845679332818910241810时间复杂度分析•结点的高度：该结点距树叶的距离•结点的深度：该结点距树根的距离•同一深度结点分布在树的同一层同高度结点可以分布在树的不同的层同一高度结点可以分布在树的不同的层•思路：按照高度计数结点数，乘以O (h ), 再求和Heapify(i ) i p y()的复杂度依赖于的高度⎣⎦∑×==n h O h n T log )()(的结点数高为h 034计数高度为h 的结点数引理n 个元素的堆高度h 的层至多存在个结点.⎥⎥⎤⎢⎢⎡+12h n 证明思路: 对h 进行归纳.归纳基础⎡h =0, 命题为真，即证堆中树叶数为归纳步骤⎥⎥⎤⎢⎢2n 归步假设对h -1为真，证明对h 也为真.35归纳基础h =0,d -1d (),-10, 树叶分布在d 和d 1层，d 层( x 个), d 1 层(y 个).Case1: x 为偶数x +=−+=+−−222211x x y x d d ⎥⎥⎤⎢⎢⎡=⎥⎥⎤⎢⎢⎡−+=+=22122)2(n x x dd y 个每个内结点有2 个儿子，树叶数为(为偶数11)x 个( x 为偶数，d -1 层以前各层结点总数2d −1 )36归纳基础（续）Case2 x 为奇数(x 为奇数，n 为偶数)+−+=+−121x x y x d −+=−1221x d ⎤⎢⎡=−+=122n n x dy 个⎥⎥⎢=222x 个37归纳步骤假设命题对于高度h -1为真，证明对于高度为h 也为真.设T 表示n 个结点的树，从T 中移走所有的树叶得到树T’, T 与T ’的关系：T 为h 的层恰好是T’ 的高为h -1 的层. n =n ’+n T’ 的结点数为n ’, n 为T 的树叶数）0(,0T’38T归纳步骤（续）令n h 表示T 中高为h 的层的结点数根据归纳基础, n 0=⎥⎥⎤⎢⎢⎡2n '⎥⎢=−=n n n n 10'2−=⎥⎦⎢⎣h h n n ⎣⎦⎤⎡=⎥⎤⎢⎡≤⎥⎤⎢⎡=⎤⎡≤=−221''n n h h n n n n ⎥⎥⎢⎢⎥⎢⎥⎢⎥⎥⎢⎢+12222h h h h 39时间复杂度分析定理3n 个结点的堆算法Build-Heap 的时间复杂性是O (n )证明：对高为h 的结点调用Heapify 算法时间是O (h ), 根据引理高为h ⎤⎡n 根据引理，高为h 的结点数至多为, 因此时间复杂度⎥⎥⎢⎢+12h ⎣logn ⎡⎦)(2)(g 01h O n n T h h ⎥⎥⎤⎢⎢=∑∞=+)()2(01n O h n O h h ==∑=+40推导⎣⎦),()(log 1h O n n T n h ⎥⎤⎢⎡=∑+⎣⎦2.log 12221n k n k n kkk h ⎡=≤≤−≤<⎥⎢−=则，若，于是令21222)(10101chch ch n T k h h k kh h k ⎥⎥⎤⎢⎢⎡+=⎥⎤⎢=∑∑−=−−=+).()()(21111n O h O hn O ch ch k h k h k=+=+=⎥⎢∑∑−+−+2222100n kk h h <<−==则，若)(22222)(101101101n O ch ch ch n T k h h k k h h k k h h k===⎥⎤⎢⎡<∑∑∑−=+−=−−−=+⎥⎢求和∞h ...]2322210[2320++++=∑=h h......]2121[...]2121[...]2121[43322+++++++++=...]2121...][21211[22+++++=2)1(121221=−=42堆排序算法堆排序算算法Heap-sort(A)1. Build-Heap(A)2. for i ←length[A] downto 23. do exchange A[1]↔A[i]3do4. heap-size[A] ←heap-size[A]−15. Heapify(A,1)p y(,)复杂性：O(n log n)Build-Heap 时间为O(n),从行2-5 调用Heapify n-1次，每次O(log n)，时间为O(n log n)43实例16141410810 87934793241211610983894712 47131014162141644实例8773 421943 1289101416101416412323…1789 1014164789 10141645排序问题的决策树考虑以比较运算作为基本运算的排序算法类，任取算法A, 输入L={x如下定义决策树, x2, …, x n}, 如下定义决策树：11．A第一次比较的元素为x i , x j，那么树根标记为i, j2．假设结点k 已经标记为i, j,假设结点经标记为(1) x i < x j若算法结束，k 的左儿子标记为输入；, x q，那么k 的左儿子标记为p,q 若下一步比较元素xp(2) x i > x j若算法结束，k的右儿子标记为输入；若下一步比较元素x, x q，那么k的右儿子标记为p,qp46一棵冒泡排序的决策树设输入为x1, x2, x3，冒泡排序的决策树如下121,22,31,31,32,12,31,2,33,2,12,3,12,1,33,1,21,3,2任意输入：对应了决策树树中从树根到树叶的一条路经，算法最坏情况下的比较次数：树深删除非二叉的内结点（灰色结点），得到二叉树叫做B-树B-B-47 B树深度不超过决策树深度，B树有n!片树叶引理引理1设t 为B-树中的树叶数，d 为树深，则t ≤2d . 证明归纳法.d =0, 树只有1片树叶，深度为0，命题为真.假设对一切小于d 是一棵深度为d 假设对切小于d 的深度为真，设T 是棵深度为d 的树，树叶数为t . 取走T 的d 层的x 片树叶，得到树T’. 则T’的深度为d −1，树叶数t ’。
