计算机算法基础 第2版 课件 第17章 平摊分析和斐波那契堆.pptx

1第17章 平摊分析和斐波那契堆概述 2平摊分析的常用方法 5动态表格 18只允许扩张的动态表格 20扩张和收缩都有的动态表格 26斐波那契堆 35可合并堆的操作 40减小关键字和删除任一结点的操作 57

21.概述斐波那契堆（Fibonacciheap）克服了二叉堆的缺点，使MST和Dijkstra算法有复杂度O(nlgn+m)。主要思路是，更新堆中数据后，不要马上修复堆，而是打上个记号。这使得每次更新只需O(1)的时间。(实际操作是切下这点为根的子树，插入到一个环中。)等到需要把最小值(或最大值)从堆中删除时，再把需要修复的地方一次性全部修复，并保证不论有多少地方要修复，只要O(lgn)的时间。这里，n是堆中元素的个数。传统的二叉堆用的是二叉树，很难支持上述作法，斐波那契堆允许一个内结点有多个儿子，但不超过O(lgn)个。斐波那契堆的构造和操作比较复杂。当问题规模小时，人们还是用二叉堆。但规模大时，斐波那契堆的优势会在应用中显现出来。

3平摊分析（amortizedanalysis）需要用平摊分析来证明斐波那契堆的复杂度，而平摊分析本身是一种分析算法复杂度的重要方法，我们先介绍平摊分析。平摊分析简介：算法往往需要对一个数据结构作一系列操作，它们使数据结构的大小随之动态地变化。所以，每一次操作所需要的时间，会因为数据结构大小不同，会非常不同。为简化分析，通常用最坏情况时一次操作所需时间来估计。例如，修复一个堆有时不需要2lgn次比较，但我们都算作2lgn次比较。这样的简化估计有时可得到足够好的复杂度，例如堆排序。但是，很多时候这个简化的估计会导致很差的结果。对n次操作所需要的时间作精确分析往往较难。平摊分析的思路是，对一次操作平均需要的时间做一个估计。

4平摊分析简介（继续）要得到精确的平均值同样难，所以，平摊分析的思路是：对一个操作平均需要的时间的上界做一个估计，使得一个操作实际需要的时间的平均值，在最坏情况下，不会超过我们估计的上界，但两者又很接近，只差一个常数因子。显然，这样的估计会足够好，因为它可精确地给出，最坏情况下，这n个操作的时间复杂度的阶。? 平摊分析就是研究如何能简单容易地得到这个上界的估计。注评：平摊分析得到的值不是算法平均情况的复杂度。算法平均情况的复杂度是考虑，算法被多次运算时，平均一次算法的运算所需要的时间。平摊分析只考虑算法运算一次，但数据结构被多次操作。它得到的是一次数据结构的操作所需的平均时间。

52.平摊分析的常用方法平摊分析的常用方法有聚集法，记账法，和势能法。聚集法(aggregateanalysis)简单地说，聚集法就是一个算总帐的方法。例17.1 堆栈操作堆栈S通常提供两种操作，并且每个操作只需O(1)时间:Push(S,x) //把元素x压入堆栈S，Pop(S) //把栈顶元素弹出。现在，我们为堆栈S加一个新的操作，Multi-Pop(S,k)。这个操作连续地把k个栈顶元素弹出。如果堆栈的元素个数少于k，则把所有元素弹出。这个操作可用下面的伪码描述：(接下页)

6例17.1 堆栈操作(继续)Multi-Pop(S,k) whileS??andk0 Pop(S) k←k–1endwhileEnd假设堆栈S一开始是空的，算法要做总共n次的Push，或Pop，或Multi-Pop操作，总共需要多少时间呢？一个简单估计是，Multi-Pop最多需要O(n)时间，所以，最坏情况下，总共需要O(n2)时间。这个估计太松了。聚集法这样分析：因为一个元素必须先被压入才可能被弹出，所以，Pop和Multi-Pop总共弹出的元素个数小于等于Push的操作次数。如果Push的次数是p，p?n，那么这n个操作总共需要的时间不超过O(p)+O(p)=O(n)。这就是为所有弹出的元素的个数算总帐的方法。

7例17.2 有k位的二进制计数器的连续增值数组A[0..k-1]对应一个有k个比特的计数器，其中A[i](0?i?k-1)存储一个二进制比特，A[0]对应最低位，A[k-1]对应最高位。如果计数器中当前的数是x，把它增值为x+1的做法是，从A[0]到A[k-1]，逐位检查，如果该位是0，则把他翻转为1，操作完成。否则，把该位从1翻转为0后再检查下一位。如果还是1，继续把1翻转为0，直到有一位是0为止。然后把0翻转为1，操作完成。例如，把二进制数1000111加1，我们需要把右边3个1翻转为0，再把下一个比特0翻转为1，从而得到1001000。如果A[0..k-1]中每个比特都是1，那么再加1的话，计数器