递归式;中位数和顺序统计

1、递归式;中位数和顺序统计报告人：陈健琦2015-04-05渐进记号渐进记号递归式递归式中位数和顺序统计量中位数和顺序统计量1.1.代换法代换法2.2.递归树法递归树法3.3.主方法主方法大纲大纲1渐近记号渐近记号渐近确界记号渐近确界记号 f(n) (g(n),用用符号符号f(n) = (g(n)来表示来表示 (g(n)= f(n)|存在存在正常数正常数c1,c2和和n0使得对所有使得对所有n n0有：有： 0 c1g(n) f(n) c2g(n) g(n)是是f(n)的渐的渐近确界近确界2f(n)的最高阶的最高阶等于等于g(n)的最高阶的最高阶 (g(n)是函数是函数的集合的集合例子：例子：a

2、n2+bn+c= (n2) n3 = (n3 )为什么渐近确界是一个函数的集合？为什么渐近确界是一个函数的集合？ 对于不同的输入，计算时间对于不同的输入，计算时间f(n)也不尽相也不尽相同，所以算法的计算时间是一个函数的集合同，所以算法的计算时间是一个函数的集合注意注意忽略系忽略系数和低数和低阶项阶项例子：例子：证明证明: : 对于对于c1NoImage证：证： (g(n)= f(n): 存在存在正常数正常数c1,c2和和n0使得对所有使得对所有n n0有：有：0 c1g(n) f(n) c2g(n) 3根据根据n0取取c1例子：例子：证明证明: : 对于对于c c2 2可取多组值可取多组值取

3、任意一组都取任意一组都可满足可满足 定义；定义；证毕证毕. . (g(n)= f(n): 存在存在正常数正常数c1,c2和和n0使得对所有使得对所有n n0有：有：0 c1g(n) f(n) c2g(n) 4渐近上界记号渐近上界记号O 给出了一个函数的上下界；当只有给出了一个函数的上下界；当只有渐近上界渐近上界时使用时使用O记号记号O(g(n) = f(n) | 存在存在正常数正常数c和和n0使得对所有使得对所有n n0有：有： 0 f(n) cg(n) 5例子：例子：an2+bn+c= O(n2) an+b=O(n2)f(n)的最高阶的最高阶小于等于小于等于g(n)的最高阶的最高阶渐近下界记

4、号渐近下界记号(g(n) = f(n) | 存在存在正常数正常数c和和n0使得对所有使得对所有n n0有：有： 0 cg(n) f(n) 6例子：例子： an2+bn+c= (n2) an3+bn+c= (n2)f(n)的最高阶的最高阶大于等于大于等于g(n)的最高阶的最高阶7渐近记号的总结渐近记号的总结渐近确界记号渐近确界记号 f(n) = (g(n) f(n)的最高阶的最高阶等于等于g(n)的最高阶的最高阶渐近上界记号渐近上界记号O f(n) = O(g(n)f(n)的最高阶的最高阶小于等于小于等于g(n)的最高阶的最高阶渐近下界记号渐近下界记号 f (n) = (g(n) f(n)的最高

5、阶的最高阶大于等于大于等于g(n)的最高阶的最高阶渐进记号渐进记号递归式递归式中位数和顺序统计量中位数和顺序统计量1.1.代换法代换法2.2.递归树法递归树法3.3.主方法主方法大纲大纲8递归式递归式 当一个算法包含对自身的递归调用时，当一个算法包含对自身的递归调用时，其运行时间通常用其运行时间通常用递归式递归式来表示来表示Merge-SortMerge-Sort过程中的最坏运行时间如下：过程中的最坏运行时间如下：解为：解为：T(n) = (nlgn)9求解递归式的方法求解递归式的方法1.1.代换法代换法2.2.递归树法递归树法3.3.主方法主方法10求解递归式的方法求解递归式的方法1.1.代

6、换法代换法2.2.递归树法递归树法3.3.主方法主方法代换法代换法在代换过程中忽略的问题：在代换过程中忽略的问题：1 1）常常假设函数自变量为整数，忽略上（下）取整常常假设函数自变量为整数，忽略上（下）取整例子：例子：T(n) = T( n/2 )+ T( n/2 ) + (n)通常将上式递归式看做为：通常将上式递归式看做为： T(n) = 2T(n/2)+ (n)适用于：解的形式很容易猜的情形适用于：解的形式很容易猜的情形11代换法代换法在代换过程中忽略的问题：在代换过程中忽略的问题：2 2）边界细节）边界细节 对于足够小的对于足够小的n来说，表示算法运行的时间的递归式来说，表示算法运行的时

7、间的递归式一般为一般为T(n) = (1)。例子：例子：通常将上式递归式看做为：通常将上式递归式看做为： T (n) = 2T (n/2)+ (n)12T (n) = (1) n = 1 T ( n/2 )+ T ( n/2 ) + (n) n 1 代换法的步骤代换法的步骤：1）猜测解的形式）猜测解的形式2）用数学归纳法找出使解真正有效的）用数学归纳法找出使解真正有效的常数常数确定确定T (n) = 2T ( n/2 )+ n的解的解O(g(n) = f (n) | 存在存在正常数正常数c和和n0使使得对所有得对所有n n0有：有：0 f(n) cg(n) 例子：例子：猜其解为：猜其解为： T

8、 (n) = O(nlgn)即证：即证： T (n) cnlgn , c 0证：证：假设上述不等式对于假设上述不等式对于 n/2 成立。成立。代入不等式得：代入不等式得： 13第第2，3步目的是步目的是找有效的常数找有效的常数cT ( n/2 ) c( n/2 )lg( n/2 )解为：解为：T(n) = (nlgn)小贴士：小贴士：对递归式进行替换：对递归式进行替换：T (n) 2c n/2 lg( n/2 ) + n 2c (n/2) lg (n/2) + n= cnlg(n/2) + n= cnlgn cnlg2 + n= cnlgn cn + n（只要（只要c 1即可）即可）猜其解为：

9、猜其解为： T (n) = O(nlgn)证：证：假设上述不等式对于假设上述不等式对于 n/2 成立。成立。确定确定T (n) = 2T ( n/2 )+ n的解的解例子：例子：目标：目标：T (n) cnlgn , c 014T ( n/2 ) c( n/2 )lg( n/2 )对于边界：对于边界： 只要找到常数只要找到常数n0,使得当使得当n n0， T (n) cnlgn 即可。即可。 假设假设T(1) = 1是唯一的边界条件是唯一的边界条件 当当n = 1时时, T (1) clg1 = 0， 而而T (1) = 1；矛盾；矛盾 当当n = 2时时，T (2) 2clg2 又又 T (

10、2) = 2 T (1) + 2 = 4 2c 4 c 2 对递归式进行替换对递归式进行替换猜其解为：猜其解为： T (n) = O(nlgn)证：证：假设上述不等式对于假设上述不等式对于 n/2 成立。成立。确定确定T (n) = 2T ( n/2 )+ n的解的解例子：例子：15 T (n) = O(nlgn)怎样才会有一个好的猜测？怎样才会有一个好的猜测？1.经验经验2.构建递归树，会有一个好的猜测构建递归树，会有一个好的猜测3.与已知的递归式类似，可猜测此递归式有类似的解与已知的递归式类似，可猜测此递归式有类似的解例例1：确定：确定T (n) = 2T ( n/2 + 17)+ n的解

11、的解 与与T (n) = 2T ( n/2 )+ n类似，类似，可直接猜测其解为：可直接猜测其解为：O(nlgn)16解为：解为：T(n) = (nlgn)小贴士：小贴士：例例2：确定：确定T (n) = 2T ( n )+ lgn的解的解 设设m = lgn,即即n = 2m T (2m) = 2T (2m/2)+ lg2m 再设再设 S(m) = T (2m),得：得： S(m) = 2 S(m/2) + m猜测其解为：猜测其解为：O(mlgm) T (n) = T (2m) = S(m) m = lgn O(mlgm) = O(lgnlglgn) T (n) = O(lgnlglgn)1

12、7代入上式得：代入上式得：忽略下取整忽略下取整则可得递归式：则可得递归式： T (n) = 2T (n1/2)+ lgn解：解：T (2m) = S(m) = O(mlgm) 解为：解为：T(n) = (nlgn)小贴士：小贴士：求解递归式的方法求解递归式的方法1.1.代换法代换法2.2.递归树法递归树法3.3.主方法主方法18求解递归式的方法求解递归式的方法1.1.代换法代换法2.2.递归树法递归树法3.3.主方法主方法递归树法递归树法使用递归树使用递归树原因原因： 递归树的方法适合产生好的猜测。递归树的方法适合产生好的猜测。使用递归树的使用递归树的作用作用： 所有层次的总代价是一个好的猜测

13、所有层次的总代价是一个好的猜测使用递归树的使用递归树的思路思路：1 1）先构建递归树，计算出总代价）先构建递归树，计算出总代价 2 2）然后用代换法进行加以验证。）然后用代换法进行加以验证。19例子例子：求解：求解T (n) = 3T ( n/4 )+ (n2) 的上界的上界1.建立递归建立递归式式： T (n) = 3T (n/4)+ cn2 2.建立建立T (n) = 3T (n/4)+ cn2 的递归的递归树树(c0 ,不妨假设不妨假设n是是4的幂的幂)1 1）建立递归树过程：）建立递归树过程：T(n)cn2T(n/4) T(n/4) T(n/4)(b)cn2T(n/16)c(n/4)2

14、c(n/4)2c(n/4)2T(n/16)T(n/16) T(n/16)(a)(c)20深度和每层结点的个数：深度和每层结点的个数：深度深度每层的每层的结点数结点数0 01 12 24n3 30 03 31 1 3 32 23 3 4nT (n) = 3T (n/4)+ cn2 的递归树如下所示：的递归树如下所示：令令a = nx,则则abn = (nx)bn = nb(nx) = nba21= n43 abn = nba第第0层代价层代价第第1层代价层代价第第2层代价层代价第第4n层代价层代价递归树每层的代价：递归树每层的代价：22递归树的总代价：递归树的总代价：无穷递减等比数无穷递减等比数

15、列的求和公式列的求和公式= = 首项首项/(1-/(1-公比公比) )猜测猜测T (n) = 3T ( n/4 )+ cn2 的解为的解为O(n2)总代价总代价232 2）用代换法进行验证）用代换法进行验证证：当常数证：当常数d 0时，时，T(n) dn2成立成立 T (n) = 3T ( n/4 )+ (n2) 由定义得：由定义得： T(n) 3d( n/4 ) 2+ cn2 3d(n/4)2 + cn2 = (3/16)dn2 + cn2 dn2 O(g(n) = f (n) | 存在存在正常数正常数c和和n0使得对使得对所有所有n n0有：有：0 f(n) cg(n) 只有只有d (16

16、/13)c，最后一步总成立。，最后一步总成立。系数：系数：24例子例子：求解：求解T (n) = 3T ( n/4 )+ (n2) 的上界的上界猜测猜测T (n) = 3T ( n/4 )+ cn2 的解为的解为O(n2)所以所以T (n) = 3T ( n/4 )+ cn2 的的解为解为O(n2)求解递归式的方法求解递归式的方法1.1.代换法代换法2.2.递归树法递归树法3.3.主方法主方法25求解递归式的方法求解递归式的方法1.1.代换法代换法2.2.递归树法递归树法3.3.主方法主方法主方法主方法主方法可以求如下递归式的解：主方法可以求如下递归式的解：T(n) = a T(n/b) +

17、f(n)渐进的正函数渐进的正函数a1b b1 1n/b代替代替 n/b 或或 n/b 26主定理：主定理：T(n) = a T(n/b) + f(n)条件：条件：a1 ,b1, f(n)渐进的正函渐进的正函数数,n/b指的是指的是 n/b 或或 n/b T(n)可能有以下的三种渐近界：可能有以下的三种渐近界：1）若）若f(n) = O(n(logba)-) ，则，则T (n)= (nlogba)2）若）若f(n) = (nlogba) ，则，则T (n)= (nlogbalgn)3）若）若f(n) = (n(logba)+) ，当，当c1, n足够大时，足够大时， 有有a f(n/b) c f

18、(n),则则T (n)= (f(n)都是将都是将f(n)与与 nlogba进行比较进行比较f(n) nlogba 直觉上的大小直觉上的大小不仅大于（小于）而且不仅大于（小于）而且多项式的大于（小于）多项式的大于（小于） 0的常数的常数f(x)多项式的大于多项式的大于g(x) : : 存在实数存在实数 0, f(x) 比比 g(x) 多一个因子多一个因子n 27例例1 1：主方法应用：主方法应用：T(n) = 9 T(n/3) + n由题可得：由题可得：a = 9 , b = 3 , f(n) = n 则则nlogba = nlog39 = (n2) f(n) = n = O(n(log39)-

19、1) = 1 T (n) = (n2) 1）若）若f(n) = O(n(logba)-) ，则，则T (n)= (nlogba)2）若）若f(n) = (nlogba) ，则，则T (n)= (nlogbalgn)3）若）若f(n) = (n(logba)+) ，当，当c1，n足够大时足够大时,有有a f(n/b) c f(n),则则T (n)= (f(n)T(n) = a T(n/b) + f(n)28符合第一种符合第一种例例2：T(n) = T(2n/3) + 1主方法应用：主方法应用：由题可得：由题可得：a = 1 , b = 3/2 , f(n) = 1 则则nlogba = nlog

20、3/21 = (1)T (n) = (lgn) 1）若）若f(n) = O(n(logba)-) ，则，则T (n)= (nlogba)2）若）若f(n) = (nlogba) ，则，则T (n)= (nlogbalgn)3）若）若f(n) = (n(logba)+) ，当，当c1，n足够大时足够大时,有有a f(n/b) c f(n),则则T (n)= (f(n)T(n) = a T(n/b) + f(n)29 f(n) = nlogba = 0 符合第二种符合第二种例例3：主方法应用：主方法应用：T(n) = 3T(n/4) + nlgn由题可得：由题可得： a = 3 , b = 4 ,

21、 f(n) = nlgn 则则nlogba = nlog43 = n0.793 f(n) = nlgn = (nlog43+) = 0.2071）若）若f(n) = O(n(logba)-) ，则，则T (n)= (nlogba)2）若）若f(n) = (nlogba) ，则，则T (n)= (nlogbalgn)3）若）若f(n) = (n(logba)+) ，当，当c1， n足够大时足够大时,有有a f(n/b) c f(n),则则T (n)= (f(n)T(n) = a T(n/b) + f(n)30符合第三种符合第三种满足第满足第3条，判断不等式是否成立条，判断不等式是否成立又又 a

22、f(n/b) = 3 f(n/4) = 3 (n/4)lg(n/4) = (3/4)n lgn - (3/4) nlg4 (3/4) nlgn = (3/4) f(n) c f(n) = c nlgn 可取可取c = 3/4，则，则T (n)= (f(n) = (nlgn )例例3：T(n) = 3T(n/4) + nlgn3）若）若f(n) = (nlogba+) ，当，当c n满足第三条满足第三条nlgn 渐近的大于渐近的大于 n不是多项式大于不是多项式大于(nlgn)/n = lgn 渐近小于渐近小于n 介于情况介于情况2)与与3)之间，之间，1）若）若f(n) = O(nlogba-)

23、 ，则，则T (n)= (nlogba)2）若）若f(n) = (nlogba) ，则，则T (n)= (nlogbalgn)3）若）若f(n) = (nlogba+) ，当，当c1，n足够大时足够大时,有有a f(n/b) c f(n),则则T (n)= (f(n)T(n) = a T(n/b) + f(n)32f(n) nlogba 求解递归式的方法求解递归式的方法1.1.代换法代换法2.2.递归树法递归树法3.3.主方法主方法解的形式很容易猜的情形解的形式很容易猜的情形递归树的总代价是一个好递归树的总代价是一个好的猜测的猜测很容易确定许多递归式的解，很容易确定许多递归式的解，但是不能覆盖

24、所有的情况但是不能覆盖所有的情况递归式总结递归式总结33渐进记号渐进记号递归式递归式中位数和顺序统计量中位数和顺序统计量1.1.代换法代换法2.2.递归树法递归树法3.3.主方法主方法大纲大纲34中位数和顺序统计量中位数和顺序统计量中位数和顺序统计量定义中位数和顺序统计量定义中位数：中位数： 中位数是有序集合中的中间元素中位数是有序集合中的中间元素顺序统计量顺序统计量： 第第i i个顺序统计量个顺序统计量 = = 该集合中的第该集合中的第i i小的元素。小的元素。 最小值最小值是该集合中的第是该集合中的第1 1个顺序统计量，个顺序统计量， 最大值最大值是该集合中的第是该集合中的第n n个顺序统

25、计量。个顺序统计量。35同时得到最大和最小值同时得到最大和最小值 独立的找出最大值和最小值，分别需要独立的找出最大值和最小值，分别需要n-1次比较，次比较，总共需要总共需要2n-2次比较。次比较。同时得到最大和最小值，最多需要同时得到最大和最小值，最多需要3 n/2 次比较。次比较。个数为偶数：成对比较个数为偶数：成对比较个数为奇数：将第一个数设为最大和最小值，成对比较个数为奇数：将第一个数设为最大和最小值，成对比较36例例1 1：1 16 68 85 59 91111集合的个数为集合的个数为偶数偶数MAX = 6 MIN = 1 个数为偶数：成对比较个数为偶数：成对比较个数为奇数：将第一个数

26、设为最大和最小值，成对比较个数为奇数：将第一个数设为最大和最小值，成对比较MAX = 8 MAX = 11 先进行一次比较，后做先进行一次比较，后做了了3(n-2)/2次比较，总共次比较，总共做了做了(3n/2)-2次比较次比较37例例2 2：1 14 48 85 59 910101212集合的个数为集合的个数为奇数奇数MAX = 1 MIN = 1 个数为偶数：成对比较个数为偶数：成对比较个数为奇数：将第一个数设为最大和最小值，成对比较个数为奇数：将第一个数设为最大和最小值，成对比较MAX = 8 MAX = 9 MAX = 12 38总共做了总共做了3 n/2 次比较次比较主元待排序列左子

27、序列 右子序列key一次划分key快速排序快速排序算法描述算法描述38287413564主元主元2 28 87 78 81 17 73 35 56 6一次调整42 28 81 17 73 35 56 648 8例：例：39求顺序统计量求顺序统计量例：选第例：选第6 6个顺序统计量个顺序统计量2 2主元主元一次划分一次划分8 87 71 13 35 56 64 42 21 13 34 47 75 56 68 81 2 3 4 5 6 7 81 2 3 4 5 6 7 84 64 68 65 6 7 8一次划分一次划分6 65 56 67 75 6 7 6 6第第6个顺序统计量个顺序统计量第第4个顺序统计量个顺序统计量4