数据结构域算法设计--divide & conqure 教案

《数据结构域算法设计--divide & conqure 教案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第2章分治法（Divide&Conquer）（算法常用技术之首）六大算法常用技术：分治法（e.g.快速排序、归并排序等）贪心法（即局部最优法，e.g.Kruscal最小生成树算法）周游法（e.g.DFS,BFS等）回朔法（e.g.8皇后问题，平面点集的凸包等）动态规划法分枝定界法（e.g.整数规划问题等）快速排序的思想：用O(n)的时间把一个规模为n的表分割为两段，前段中的数据元素均小于后段中的数据元素，然后对分割后所得的两个小一点的表采用同样的方法分别进行排序；当两个小表排好之后，整个表的排序也就完成了。（思考问题：如何证明快速排序的平均

2、时间复杂度为Q(n㏒n)?提示：考虑“逆序”的个数。）分治法的要领分治法是把一个规模较大的问题分解为若干个规模较小的子问题，这些子问题相互独立且与原问题同类；首先求出这些子问题的解，然后把这些子问题的解组合起来得到原问题的解。由于子问题与原问题是同类的，故使用分治法很自然地要用到递归。因此分治法分三步：1将原问题分解为子问题（Divide）2求解子问题（Conquer）3组合子问题的解得到原问题的解（Combine）分治法举例：给定n个数据元素，要找出其中的最大元和最小元。简单直观的方法：一个一个地找，用n-1次比较来找出最大元，再用n-2

3、次比较来找出最小元。比较次数（基本运算）为2n-3次。用分治法如何求解？当n=2时，一次比较就可以找出两个数据元素的最大元和最小元。当n>2时，可以把n个数据元素分为大致相等的两半，一半有ën/2û个数据元素，而另一半有én/2ù个数据元素。先分别找出各自组中的最大元和最小元，然后将两个最大元进行比较，就可得n个元素的最大元；将两个最小元进行比较，就可得n个元素的最小元。因此算法的时间复杂度为：T(n)=此方程可用主定理求解：a=2,b=2,f(n)=2,=n1,f(n)比的量级低（第一种情况）；所以可得T(n)=Q()=Q(n)。但此法还

4、不够精确。（简单直观的算法的时间复杂度也只有2n-3。）设n=2k,根据递归方程有T(2k)=2T(2k-1)+2,令T(2k)=g(k)（函数变形法），则有g(k)=2g(k-1)+2,从而有g(k-1)=2g(k-2)+2，g(k-2)=2g(k-3)+2，…不断使用代入法可得：T(n)=T(2k)=g(k)=2(2g(k-2)+2)+2=22g(k-2)+22+2=23g(k-3)+23+22+2=。。。。。。=2k-1g(1)+2k-1+…+23+22+2=n/2*T(2)+(2k-2)=n/2+n-2=3n/2-2,即T(n)=3

5、n/2-2。当n¹2k时，则n可表为若干2的正整数幂之和，（e.g.42=32+8+2），若n是偶数，则算法的时间复杂度仍可达到3n/2-2。e.g.对n=42，将元素分为32个一组，8个一组和2个一组共3组后，各组找出最大、最小元分别需要46，10和1次比较，3个最大元用2次比较即可得整体最大元，同理3个最小元用2次比较即可得整体最小元，故有46+10+1+2+2=61,而3n/2-2=3*42/2-2也等于61，故的确是3n/2-2。一般地，当n¹2k但为偶数时，则可将n分解为若干个2的正整数幂之和：n=2m1+2m2+…+2mk且m1

6、>m2>…>mk³1，对规模为ni=2mi的每组元素，找出最大、最小元需要3ni/2-2次比较,故获得k组各自的最大、最小元需要=3n/2-2k；然后用2k-2次比较就可从每组的最大元、最小元（均为k个）中求出整体的最大元和最小元，故全部的比较次数仍为3n/2-2。当n¹2k但为奇数时，则可将n分解为若干2的正整数幂之和加1：n=2m1+2m2+…+2mk+1且m1>m2>…>mk³1，由于2m1+2m2+…+2mk=n-1，故=3(n-1)/2-2k；注意此时共有k+1组最大、最小元，取得整体解还需比较2k次（单独的一个元素既是该组最大元

7、，也是该组最小元），故全部的比较次数为3(n-1)/2即3n/2-3/2，亦可看成为é3n/2-2ù。已经证明，设A是能够在规模为n的数据元素集合中找出最大元和最小元的任何一个算法，则必存在一个实例，对该实例，A算法至少需要é3n/2-2ù次比较，即é3n/2-2ù是找最大最小元算法的时间复杂度下界。因此，从比较次数最少的意义上来讲，找最大最小元的分治法算法已经达到最优。虽然从理论上看，将n分解为若干2的正整数幂之和可以获得最少的比较次数，但实际计算时为简单起见，一般把n个数据元素分为大致相等的两半：一半有ën/2û个数据元素，而另一半有é

8、n/2ù个数据元素。先分别找出各自组中的最大最小元（如组中只有一个元素，则其既是最大元又是最小元）；再将两个最大元和两个最小元分别进行比较，于是就可得到n个元素的最大元和最小元。