算法设计与分析_04算法分析举例

1、2022-3-9算法设计与分析演示稿 纪玉波制作(C)1算法设计与分析算法设计与分析算法分析举例算法分析举例2022-3-9算法设计与分析演示稿 纪玉波制作(C)2算法分析举例算法分析举例 本节举几个对具体算法进行分析的例子，可以由此学习分析的方法，举一反三再分析其它的算法。2022-3-9算法设计与分析演示稿 纪玉波制作(C)3例1. 堆阵排序1堆阵 堆阵排序（Heap sort, 1964年Robert W. Floyd 和J.Williams共同设计，1978年Robert W. Floyd获图灵奖）是利用二叉树的一种排序方法。堆(Heap)也译为堆或堆垒,是与二叉排序树不同的一种二叉树

2、，它的定义为：一个完全二叉树(完全二叉树：各层都是满的，只是最下面一层从右边起连续缺几个结点)，它的每个结点对应于原始数据的一个元素，且规定：如果一个结点有子结点，此结点数据必须大于或等于其子结点的数据。由此可见，堆是完全二叉树，且规定了父结点和子结点数据之间必须满足的条件。 2022-3-9算法设计与分析演示稿 纪玉波制作(C)4 由于堆阵是完全二叉树，采用将结点顺序编号存于一维数组中的表示法较链接表示法节省存储也便于运算。设某堆的结点数共有n个，顺序将它们存人一维数组K中，下标从1到n。根据顺序表示二叉树的特点，除下标为1的结点是整个树的根结点而没有父结点以外，其余下标为j的结点（2jn）

3、都有父结点，父结点的下标为i= 。故堆阵的条件可以表示成: KiKj 当2jn 和i= 由堆的定义可知，其根结点（即在数组中下标为1的结点）具有最大的数值，堆阵排序就是利用这一特点进行的。堆阵排序过程分为构成堆和利用它来排序两个阶段，下面分别进行介绍。2/ j2/ j2022-3-9算法设计与分析演示稿 纪玉波制作(C)52构成堆阵的过程 可以采用两种方法构成堆阵。第一种方法是从根结点起逐个插入结点，在插入结点过程中进行父子结点数据比较和必要的互换调整，使之总满足堆的条件；第二种方法则是先把所有数据按任意次序置入完全二叉树的各结点中，然后由下而上逐层进行父子结点数据比较，进行必要的互换调整，直

4、至使其最后完全满足堆的条件，数据的比较调整可以使用“筛”运算进行。筛运算从最末尾结点（下标为n）的父结点（下标为 ）开始，向前逐结点进行，直至筛完根结点即形成此堆阵。筛每个结点时，将其数值与其两个子结点中数值较大者进行比较，如小于子结点数值，则与之进行互换，互换后又将它看成父结点，再与下一层的子结点进行比较，如此做下去，直至不小于其子结点的数值或已筛到端结点而不再有子结点了，此数据的筛运算即完成。2/n2022-3-9算法设计与分析演示稿 纪玉波制作(C)63利用堆阵排序 由于在一个堆中根结点数据总是所有数据中之最大者，利用堆阵排序的方法是从根结点逐个取出数据，每次将新的元素再提到根结点，如此

5、反复进行。为了节约存储，要求排序得到的有序数据序列仍存放于原数组中，故将从根结点取出的数据由数组的末端起逐单元存放。每存放一个数据，同时将原在该单元的数据换到根结点，但这样互换后一般会破坏堆的条件，为此，需对根结点再做一次筛运算，就又可形成新的满足条件的堆。随着数组末端存放的由堆中取出的数据越来越多，堆的结点数逐渐减少，当到取出了(n-1)个数据，堆阵只剩下一个根结点，此最后一个数据一定是全部数据中的最小者，堆阵排序过程即全部结束。2022-3-9算法设计与分析演示稿 纪玉波制作(C)7 4时间复杂性分析 堆阵排序分为建立堆阵和利用堆阵排序两大步骤。设堆阵有r个满层，元素个数n=2r-1。最坏

6、的情况假设每个元素都需要从原来位置筛到堆阵的最底层，仅原来在最底层的不必筛，这样一来最上层的一个元素要下降r-1层；第二层的两个元素要下降r-2层；中间第i层2(i-1)个元素要下降r- I层；下面倒数第一层，也即第r-1层的2(r-2)个元素下降一层。每筛下一层要进行两次比较（先左右两子节点相比，然后此元素与其中较大者比）。因此在最坏的情况下，为了建立堆阵所需要的比较次数为：) 1 (2) 3(4)2(2) 1( 1 (2)(2211)2() 1(ririrrrir2022-3-9算法设计与分析演示稿 纪玉波制作(C)8 (上式中共有(r-1)项，第一项包括(r-1)个 1，第二项包括(r-

7、2)个 2， 第二项包括(r-3)个 3，最后一项是一个 2(r-2),将它们重新组 合后可得下式) )2421 ()421 ()21 ()1(2)2( r 2020)1(2) 12(2)2221 (2rkrkkk )1(2222(2)1(32rr )1()22(2rr （ 因10212rkkr） ) 1) 1(log(2) 1(2nn （因12rn） nnn2) 1log(22 （当n较大时）2022-3-9算法设计与分析演示稿 纪玉波制作(C)9 下面看利用堆阵排序所需要的比较次数。排序时由后向前顺次将元素与根结点对换，并将换到根结点的元素筛到合适的位置处，如果逐个进行，堆阵越来越小，直至

8、排序完毕。设在某一步堆阵有i个元素，其深度为 ，最坏情况将根元素筛到堆阵最下层需要比较次为 ，故最坏情况排序过程的总比较次数为：1log i 11log2nii 因13log2log，27log6log5log4log ,315log9log8log当 n 恰 为 2 的 整 数 次 方 时 ， 上 述 合 式 为 ： 1log1112lognjjniji（ 例 如 n=16 时 ， 上 式 为 （ 1 2+2 4+3 8） =312jjj）ilog22022-3-9算法设计与分析演示稿 纪玉波制作(C)10若n不恰为2的整数次方时，则后面几项表成： )2(loglognn（例如n=19时，比

9、n=16多出三项，每项均为419log，恰好是4（19-24）=43=12）因为 112012011112011111112222) 1(2)22(2kjkjjkjjjkjkjjjkjjjkjjjjjjjj 222222) 1() 12( 22) 1(11kkkkkkkkk故排序总的比较次数为： ) 22log(2)2(log222log(21loglog1loglognnnnnnnnn nnn2log2 （当n较大时） （+2 n，建立堆栈的比较次数）2022-3-9算法设计与分析演示稿 纪玉波制作(C)11 因此堆阵排序总的比较次数当n较大时最坏情况为2nlogn(其复杂性为O(nlogn

10、)，为排序问题下界的两倍。虽然此排序算法时间上不是最优，但它是“就地”进行运算，也不需要指示字分量，故所占空间比较节省。2022-3-9算法设计与分析演示稿 纪玉波制作(C)12例2. 快速排序 快速排序(Quick sort)是1962年由霍尔（Hoare）提出的，故也称为霍尔快速排序。这是一种基于分部分进行互换的排序方法，其基本思想是将所有数据逐步划分成越来越多的许多小部分，每划分一次，以后的互换只在划分成的各小部分中进行，再将各小部分划分成更小的部分。此算法是把一个大问题划分成一些子问题，对这些子问题再用同样的算法递归地进行处理，最后将所有子问题的解答合在一起即得到原来大问题的解，这种处

11、理问题的算法叫做分治法（Divide and conquer）。2022-3-9算法设计与分析演示稿 纪玉波制作(C)13 进行快速排序运算，首先任选其中一个数据（例如选第一个数据）作为标准，经过一定的互换运算，令它将其余的数据划分为两部分，它本身处于这两部分数据之间，并且它前面的所有的数据均小于或等于它，它后面的所有的数据均大于或等于它。由此可看出两点：第一，此数据的位置就是它最终的合适位置，进一步的运算过程中此数据即不必再动；第二，以后的排序运算只需在划分成的每部分里进行，两部分之间不会再有数据互换。第一次划分以后，再用相同的算法对划成的部分进行类似的运算，即从每部分中任选一个数据将其划分

12、成更小的两部分，依此递归地做下去，直至每个小部分中的数据个数均不超过一个为止，排序过程即结束。2022-3-9算法设计与分析演示稿 纪玉波制作(C)14 如原始数据已存于一维数组K中，设进行比较的两个数据所在单元下标分别为i和j。初始时i指向数组中第一个数据，j指向第末个数据。i先不动使j逐步前移，每次对二者的数据进行比较，当遇到Ki大于Kj的情况时，即将二者对调位置；然后令j固定使i逐步后移做数据比较，再遇到Ki大于Kj时又进行位置对调；以后又是i不动使j前移做数据比较；如此反复进行，直至i与j两者相遇为止。下面是一实例：2022-3-9算法设计与分析演示稿 纪玉波制作(C)15(13) 1

13、5 7 10 20 4 8 (19)(13) 15 7 10 20 4 (8) 19 8 (15) 7 10 20 4 (13) 19 8 (13) 7 10 20 (4) 15 19 8 4 (7) 10 20 (13) 15 19 8 4 7 (10) 20 (13) 15 19 8 4 7 10 (20) (13) 15 19 8 4 7 10 (13) 20 15 19 第一趟比较2022-3-9算法设计与分析演示稿 纪玉波制作(C)16 其中括号中的数据表示正进行比较的两个数据，左面一个的下标为i，右面一个的下标为j。最后一行只有一个括号，说明i与j相等了，此单元即是作为标准的数据（

14、13）之最终位置。 从图中可以看出，作为标准的数据（13）要多次与别的数据进行比较和互换。为了节约运算时间，可先将其取出给一局部工作变量赋值，以后只移动别的数据，它不真正参加“互换”，一直到i=j时才将其置入最终合适的位置处。2022-3-9算法设计与分析演示稿 纪玉波制作(C)17(1 13 3) 15 7 10 20 4 8 19(8 8) 4 7 10 13 20 15 19(7 7) 4 8 (1 10 0) 13 20 15 19 4 7 8 10 13 (2 20 0) 15 19 4 7 8 10 13 (1 19 9) 15 20 4 7 8 10 13 19 15 20 每一

15、趟比较2022-3-9算法设计与分析演示稿 纪玉波制作(C)18最坏情况分析：若每次选作标准的元素恰好是其中最小的一个，则划分出的两组数据，一组为零个元素，另一组只比原来少一个，这样所需的趟数最多，如下表所示：已选取元素剩余元素个数比较趟数本趟比较次数1x) 1( n1) 1( n21xx) 2( n2) 2( n321xxx) 3( n3) 3( n1321,nxxxx1) 1( n1因此所需比较次数为： )() 1(21211nOnnini2022-3-9算法设计与分析演示稿 纪玉波制作(C)19 平均情况分析：此处除了为了具体推导出平均情况复杂性外还有两个目的：一是可以看出平均情况复杂性

16、分析较最坏情况复杂性分析要困难得多；二是举例说明递归方程的解法。 设选作标准的元素将数据分成两组，一组有k个元素，另一组有（n-k-1）元素。由于要考虑各种可能的情况，k值可能为0（n-1），相应的另一组的个数则为（n-1）0。令对n个元素进行快速排序所需要的平均比较次数为C（n），并设k的各种取值出现的概率相等，则C（n）为各种k的取值的平均值10)1()() 1(1)(nk2n knCkCnnnC2022-3-9算法设计与分析演示稿 纪玉波制作(C)20 式中括号中第一项为第一趟所需的比较次数，后面两项分别为左右两部分数据继续进行快速排序所需的平均总比较次数， 。 这是一个递归方程，常可用

17、两种解法：第一种是试猜法，即假设一个带有若干待定常数的函数，代入方程中导出这些常数，但这种方法假设这个函数要有一定经验；另一种方法是直接利用递归方程的特点求解。我们现介绍后一种方法。而对于2n有0)(nC2022-3-9算法设计与分析演示稿 纪玉波制作(C)21上式中求和的第一项不随k改变，其平均值即为它本身：101) 1(1nknnn后两项的求和恰好相等，只是次序不同，因：k012n-2n-1C(k)C(0)C(1)C(2)C(n-2)C(n-1)C(n-k-1)C(n-1)C(n-2)C(n-3)C(1)C(0)故上述公式可以表示成 10)(2) 1()(nk2n kCnnnC用n乘左右两

18、边，得 10)(2) 1()(nk kCnnnnC令1nn 10)(2) 1()() 1(nk kCnnnCn2022-3-9算法设计与分析演示稿 纪玉波制作(C)22将 此 两 式 相 减 ， 得 )(22)()1()1(nCnnnCnCn即 nnCnnCn2)()2()1()1(等 式 两 边 用)2)(1(nn除 ， 得 )2)(1(21)(2)1(nnnnnCnnC令 )2)(1(2)(,1)()(nnnnbnnCnd， 则 )1(2)1(ndnnC2022-3-9算法设计与分析演示稿 纪玉波制作(C)23上 式 简 化 为 )()()1(nbndnd这 个 递 归 方 程 可 以 一 直 推 下 去 ， 并 考 虑 到 有 02)1()1(Cd， 故 )()()1(nbndnd )()1()1(nbnbnd )()1()1(nbnb