扫码下载官方App
算法设计与分析之进阶篇
所属微专业：
算法设计与分析之进阶篇算法设计与分析之入门篇见：
证书要求 证书规则将在开课前发布
预备知识 集合论图论，高等数学，数据结构与算法。
授课大纲 算法设计与分析之进阶篇第一周 从排序看算法设计与分析1-1 从排序看算法分析1-2快速排序深入剖析1-3 问题复杂度下界1-4 基于比较的排序算法的时间复杂度下界第二周 再论动态规划2-1 优化子结构的分类2-2 三角剖分问题2-3 编辑距离问题2-4 &0-1背包问题第三周 图上的动态规划算法3-1 最优二分搜索树3-2 树的独立集合3-3 任意两点最短路径问题第四周 贪心法与拟阵4-1 最小生成树算法4-2 拟阵概述4-3 从拟阵看任务安排问题第五周 再论搜索5-1 剪枝方法论与人员安排问题5-2 旅行商问题5-3 A*算法第六周 平摊分析6-1 平摊分析原理6-2聚集方法6-3 会计方法6-4 势能方法6-5 动态表操作的平摊分析 `
参考资料 殷建平, 徐云, 王刚, 刘晓光, 苏明, 邹恒明, 王宏志 (译). 算法导论. 机械工业出版社, 2012. 12.
所属微专业
所属系列课程
网易公司()旗下实用技能学习平台。与优秀讲师、专业机构、院校合作，为您提供海量优质课程，以及创新的在线学习体验，帮助您获得全新的个人发展和能力提升。
关注我们：
& 网易公司 版权所有 上传我的文档
 下载
 收藏
该文档贡献者很忙，什么也没留下。
 下载此文档
正在努力加载中...
算法 平摊分析
下载积分：1500
内容提示：算法 平摊分析
文档格式：TXT|
浏览次数：6|
上传日期： 13:30:03|
文档星级：
该用户还上传了这些文档
算法 平摊分析
官方公共微信1365人阅读
数据结构与基础算法（14）
1.平摊分析是什么
平摊分析是一种算法分析的手法，其主要思路是：对若干条指令（通常O(n)条）整体进行考虑其时间复杂度（以获得更接近实际情况的时间复杂度），而不是逐一考虑执行每条指令所需的时间复杂度后再进行累加。
对于一个操作的序列来讲，平摊分析（Amortize Analysis）得出的是在特定问题中这个序列下每个操作的平摊开销。一个操作序列中，可能存在一、两个开销比较大的操作，在一般地分析下，如果割裂了各个操作的相关性或忽视问题的具体条件，那么操作序列的开销分析结果就可能会不够紧确，导致对于操作序列的性能做出不准确的判断。用平摊分析就可以得出更好的、更有实践指导意义的结果。因为这个操作序列中各个操作可能会是相互制约的，所以开销很大的那一、两个操作，在操作序列总开销中的贡献也会被削弱和限制。所以最终会发现，对于序列来讲，每个操作平摊的开销是比较小。平摊分析的输入是问题的具体条件以及若干个有相互关联的具体动作的序列，输出是，在该问题的条件下，这个动作序列的每一个动作（不管具体它是什么）的平摊性能开销并不等于最大开销动作的最坏时间（不再需要考虑具体动作，只需要知道每个动作可能是平摊小开销的）。
下面我们来看一个关于动态表的具体例子：
我们经常会遇到这样的情况：无法预先知道有多少对象需要存储。因此无法准确地事先分配好足够的内存并保证内存是大致足够的。事先分配的内存要么可能不足，要么太多以致浪费。
对于这种情况，我们可以采用动态表的策略来应对。就是一开始分配一定量的内存A，如果在向这个内存内继续增加对象时发现空间不足的话，就重新分配一块比原来大的内存B（就定B比A要大两倍吧），把原内存A中所有的对象都复制到内存B中，然后把新加入的对象增加到B的空余位置中，最后把内存A释放掉。同样，如果从内存中称除某个对象时，发现此空间内所存的对象太少，出现空间浪费时，就分配一块新的更小的内存（先假设新内存是原内存的二分之一），把原内存中的对象复制过来，并释放原内存给其它的程序使用（C++标准库中的vector等，就用了这样的策略）。
我们先来看插入操作的伪代码：
TABLE-INSERT (T , x)
1 if size[T ] = 0 then
2 allocate table[T] with 1 slot
3 size[T] ← 1
4 if num[T] = size[T] then
5 allocate new-table with 2 · size[T] slots
6 insert all items in table[T] into new-table
7 free table[T]
8 table[T] → new-table
9 size[T] → 2 · size[T]
10 insert x into table[T]
11 num[T] → num[T] + 1　　在这个操作中，如果插入时，原内存块还有足够的空间，那就只要把新插入的x放到未使用的空间上（空间的使用是连续的，动作就是伪代码中的第10行），这样，需要的时间仅仅是常数时间O(1)。如果插入对象时，原内存块已经没有空间再容纳新成员了，这时就需要分配新的空间，把原内存的数据复制过去，释放原内存，然后再进行插入动作（如伪代码中的5-9行）。这种情况下，需要的时间候，就是原内存的长度相关（因为要依次拷贝原内存中的每一个对象），这是一个O(n)时间的操作。因此，TABLE-INSERT操作的最坏时间复杂度是性线的O(n)。
好，例子的情况到这里已经描述完了。现在我们来看，如果对一个动态表进行一个由n个TABLE-INSERT操作组合起来的动作序列，那么这个序列的操作性能是怎么样的呢？
乍一想，我们可能会认为，每个TABLE-INSERT的最坏性能是O(n)，n个TABLE-INSERT操作如果恰好每个操作都出现了最坏性能，那么整个操作序列的最差时间复杂度就是O(n2)。虽然这个结果是这个操作序列的一个最差时间复杂度上界，但实际上，这个上界是不够紧确的。
我们假设一开始这个表是空的，然后用TABLE-INSERT向这个表中依次插入n个对象。仔细一想，就会发现，这个操作序列中的n个TABLE-INSERT是不可能连续n次出现最坏性能的，甚至，出现最坏性能的机会是比较小的。假设ci是第i次插入时的时间，那么很容易就可以分析出来，ci只i等于2的整数次幂时，才会出现比较大的值（值为i），除此以外，ci都是常数1。我们把ci进行求和，就可以得出总的时间计算式
所以，这个操作序列的最坏时间复杂度其实是O(n)。
原因就在于，这个TABLE-INSERT虽然偶尔会出现线性时间复杂度的操作，但这种情况，在这个问题中出现的机会很少（只有i等于2的整数次幂时），而其它情况下，TABLE-INSERT的操作都是常数时间，这些情况足以将TABLE-INSERT偶尔出现的&恶劣&行为的影响平摊掉。使得对于整个序列来说，最坏时间复杂度仍然保持在比较好的水平下，每个操作的平摊性能也显得很优良（每个操作都O(1)的）。（这个问题更严谨的分析应该看《算法导论》书中17.4部分）
同样的，TABLE-DELETE操作与TABLE-INSERT操作的分析是极为类似的。这里就不再单独讨论。
但有意思的是，如果是由TABLE-DELETE与TABLE-INSERT两种操作来组成一个操作序列的话，结果会是怎么样的呢？我们先假设，a一个动态表的装载因子，它是用内存块中对象个数除以内存块可存储的对象总个数得到的。那么，如果动态表每次扩充都变成原来大小的两倍的话，每个TABLE-INSERT之后，装载因子都是0.5；同样，每次缩减时成缩减成原来的1/2的话，而每次TABLE-DELETE之前，表的装载因子也为0.5。与原来单纯的INSERT序列或DELETE序列不一样的是，在上面这段话中描述的情况下，最差时间复杂度将会是O(n2)。为什么呢？？因为具体问题的条件变化了，这两个操作之间的制约也减弱了，比如，可能是以下这么一种操作序列：
先进行插入，一直到插入动作进行时表进行了扩张，之后的操作则是：
　　D、D、I、I、D、D、I、I、D、D、I、I......
这时，分析可知，这个表将在这些动作间不断地扩张和缩减。这个序列中之后的操作每一个都是O(n)时间。因此，总的时间复杂度是O(n2)。之所以会这样（不再是O(n)了），是因为，这个操作序列和条件下，已经不能保证有足够的O(1)的操作来平摊掉O(n)操作的开销， O(n)操作的出现机会也不再受到控制。
有一个办法可以改进，就是动态表在TABLE-DELETE在装载因子是0.25（或其它可能值）而不是0.5时才进行缩减。这样，又能恢复类似之前的分析和结果了（最差时间复杂度为O(n)）。
从这个例子也可以看出：
这就是平摊分析观察问题的角度，它考查的是一个操作序列，并且把操作之间的相互影响，以及问题的条件制约考虑进来得出性能结论。这比起割裂各操作的相互限制以及问题具体条件来分析更具指导意义。
2.平摊分析的三种常用技术（转自：http://blog.csdn.net/touzani/article/details/1696399）
a.聚集分析（平摊分析最常用的手法）
中心思想：从全局来整体考虑时间复杂度，把O(n)条指令的耗费（时间复杂度）分为几类；分别计算O(n)条指令中每一类耗费的总和，然后再把各类耗费总加起来。
例子：栈操作
PUSH(S, x)：将x压入S（执行需要O(1)）
POP（S）：弹出栈顶（执行需要O(1)）
MULTIPOP（S, k）：弹出栈顶k个对象（最坏情况下，MULTIPOP执行一次需要O(n)时间）
由n个PUSH， POP和MULTIPOP操作序列
分析：每个操作的最坏情况时间是O（n）（都是MULTIPOP，且都是MULTIPOP的最坏情况），因此n个操作的序列的代价是O (n2)？
虽然这一分析正确，但这个界不够紧确。如何分析？
把Pop, Multi-Pop的耗费分为两类： 1. 出栈操作需要的耗费；2. 非出栈操作（判断栈中的元素个数）需要的耗费。
一条Multi-Pop指令的非出栈操作耗费为O(1)，（Pop指令没有非出栈操作的耗费）故n条指令的第2类（非出栈操作）的耗费为O(n)。
出栈操作需要耗费的分析：一个元素在出栈之前必定首先要进栈，故出栈元素的个数一定小于等于进栈元素的个数。∵共有n条指令，∴进栈操作指令Push(x,S)最多n条。Push(x,S)指令每次只能使一个元素进栈，故进栈元素最多为n。由于出栈元素个数小于进栈元素个数，因此全部Pop及Multi-Pop指令中取元素出栈的操作最多为n ；故出栈操作需要的耗费也为O(n)。由此得总耗费也为O(n)。
b.记账方法
中心思想：在计算A指令的耗费时，将B指令的全部或部分耗费提前计算，一并算作A指令的耗费。于是计算B指令耗费时此部分就无需再算。
栈操作的最主要工作是：进栈和出栈。由于一个元素的出栈必然在进栈之后，故计算进栈指令耗费时可将进栈元素的出栈耗费一并算入，这样，执行任一元素的出栈指令时就不需要再计算出栈耗费了。（因为费用已提前计算过。）
例子：栈操作
实际代价：
MULTIPOP min(k, s)
现在对它们赋予以下的平摊代价：
PUSH: 2（包括元素的进栈与该元素出栈的耗费）
POP: 0（任一元素出栈的耗费已经被push指令提前计算了）
MULTIPOP: 1（该代价为执行MULTIPOP时，对栈中元素个数进行判断所需的耗费，任一元素的出栈耗费已经被push指令提前计算了）&
因为一条指令的最大平摊代价为2，所以n条指令最大的平摊代价不超过2n。
3.势能分析（不怎么明白，原搬算法导论）
在平摊分析中，势能方法（potential method）不是将已预付的工作作为存在数据结构特定对象中存款来表示，而是表示成一 种“势能”或“势”，它在需要时可以释放出来，以支付后面的操作。势是与整个数据结构而不是其中的个别对象发生联系的。
对一个初始数据结构D0 执行n个操作。对每个i，设ci为每个操作的实际代价，Di 为对数据结构Di-1执行第i个操作的结果. 势函数Φ 将每个数据结构Di 映射为一个实数Φ(Di), 即与Di相联系的势. 第i个操作的平摊代价ai根据势函数Φ 定义为
ai ＝ ci ＋ Φ(Di) － Φ(Di-1)
每个操作的平摊代价为其实际代价ci加上由于该操作所增加的势。
n个操作的总的平摊代价为
∑ai ＝ ∑ci ＋Φ(Dn) － Φ(D0)
如果我们能定义一个势函数Φ使得对所有n，有Φ(Dn) ≥ Φ(D0), 则总的平摊代价∑ai就是总的实际代价∑ci的一个上界。通常为了方便起见定义Φ(D0) ＝ 0。
直观上看，如果第i个操作的势差Φ(Di) - Φ(Di-1)是正的，则平摊代价ai表示对第i个操作多收了费，同时数据结构的势也随之增加了。如果势差是负值，则平摊代价就表示对第i个操作的不足收费，这是通过减少势来支付该操作的实际代价。
平摊代价依赖于所选择的势函数Φ。不同的势函数可能会产生不同的平摊代价，但它们都是实际代价的上界。最佳势函数的选择取决于所需的时间界。
例子：栈操作
定义栈上的势函数Φ为栈中对象的个数。开始时要处理的空栈D0，且Φ(D0)＝0。因为栈中的对象数始终时非负的，故在第i个操作后，栈Di就具有非负的势。
以Φ表示的n个操作的平摊代价的总和就表示了总的实际代价的一个上界。
现在计算各个操作的平摊代价。
如果作用于一个包含s个对象的栈上的第i个操作是PUSH：
则势差为Φ(Di) － Φ(Di-1) = (s+1) – s = 1
这个PUSH操作的平摊代价为ai ＝ ci ＋ Φ(Di) － Φ(Di-1) = 1+1=2
假设栈上的第i个操作是MULTIPOP(S, k). 该操作的实际代价为min(s, k).
势差为Φ(Di) － Φ(Di-1) = - min(s, k)
因此MULTIPOP操作的平摊代价为
ai ＝ ci ＋ Φ(Di) － Φ(Di-1) ＝ min(s, k) - min(s, k) = 0
类似POP操作的平摊代价也是0。
三中栈操作的每一种的平摊代价都是O(1)， 这样包含n个操作的序列的总平摊代价就是O(n)。已经证明n个操作的平摊代价的总和是总的实际代价的一个上界。所以n个操作的最坏情况代价为O(n).
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：68189次
积分：1362
积分：1362
排名：千里之外
原创：65篇君，已阅读到文档的结尾了呢~~
[业务]算法 平摊分析
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
[业务]算法 平摊分析
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer--144.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口}