算法设计与分析_04算法分析举例ppt课件.ppt

《算法设计与分析_04算法分析举例ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法设计与分析——算法分析举例2021/7/301算法设计与分析演示稿纪玉波制作(C)算法分析举例本节举几个对具体算法进行分析的例子，可以由此学习分析的方法，举一反三再分析其它的算法。2021/7/302算法设计与分析演示稿纪玉波制作(C)例1.堆阵排序1．堆阵堆阵排序（Heapsort,1964年RobertW.Floyd和J.Williams共同设计，1978年RobertW.Floyd获图灵奖）是利用二叉树的一种排序方法。堆(Heap)也译为堆或堆垒,是与二叉排序树不同的一种二叉树，它的定义为：一个完全二叉树(完全二叉树：各层

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

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

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

5、于在一个堆中根结点数据总是所有数据中之最大者，利用堆阵排序的方法是从根结点逐个取出数据，每次将新的元素再提到根结点，如此反复进行。为了节约存储，要求排序得到的有序数据序列仍存放于原数组中，故将从根结点取出的数据由数组的末端起逐单元存放。每存放一个数据，同时将原在该单元的数据换到根结点，但这样互换后一般会破坏堆的条件，为此，需对根结点再做一次筛运算，就又可形成新的满足条件的堆。随着数组末端存放的由堆中取出的数据越来越多，堆的结点数逐渐减少，当到取出了(n-1)个数据，堆阵只剩下一个根结点，此最后一个数据一定是全部数据中的最小者，堆阵排

6、序过程即全部结束。2021/7/306算法设计与分析演示稿纪玉波制作(C)4．时间复杂性分析堆阵排序分为建立堆阵和利用堆阵排序两大步骤。设堆阵有r个满层，元素个数n=2r-1。最坏的情况假设每个元素都需要从原来位置筛到堆阵的最底层，仅原来在最底层的不必筛，这样一来最上层的一个元素要下降r-1层；第二层的两个元素要下降r-2层；……；中间第i层2(i-1)个元素要下降r-I层；……；下面倒数第一层，也即第r-1层的2(r-2)个元素下降一层。每筛下一层要进行两次比较（先左右两子节点相比，然后此元素与其中较大者比）。因此在最坏的情况下，

7、为了建立堆阵所需要的比较次数为：2021/7/307算法设计与分析演示稿纪玉波制作(C)2021/7/308算法设计与分析演示稿纪玉波制作(C)下面看利用堆阵排序所需要的比较次数。排序时由后向前顺次将元素与根结点对换，并将换到根结点的元素筛到合适的位置处，如果逐个进行，堆阵越来越小，直至排序完毕。设在某一步堆阵有i个元素，其深度为，最坏情况将根元素筛到堆阵最下层需要比较次为，故最坏情况排序过程的总比较次数为：2021/7/309算法设计与分析演示稿纪玉波制作(C)2021/7/3010算法设计与分析演示稿纪玉波制作(C)因此堆阵排序

8、总的比较次数当n较大时最坏情况为2nlogn(其复杂性为O(nlogn))，为排序问题下界的两倍。虽然此排序算法时间上不是最优，但它是“就地”进行运算，也不需要指示字分量，故所占空间比较节省。2021/7/3011算法设计与分析演示稿