算法2013s平摊分析.pptx课件.pptx

《算法2013s平摊分析.pptx课件.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法设计与分析2021年7月31日讲授内容：平摊分析教　　师：胡学钢、吴共庆纲要动态表聚集分析法记账法势能法7/31/2021算法设计与分析-动态规划2目标:使表尽可能的小，但是还足够大不会溢出（或者变为低效率）。问题:如果我们不能预先知道合适的大小应该怎么办？答案:动态表.思路:每当表溢出的时候，通过分配（用malloc或者new）一个新的更大表使其增长。将原来表中的所有项都移动到新表中，然后释放旧表的内存。哈希表应该多大?1.插入2.插入溢出动态表举例1.插入2.插入溢出动态表举例1.插入2.插入动态表举例1.插入2.插入3.插入溢出1.插入2.插入3.插入溢出动态

2、表举例1.插入2.插入3.插入溢出动态表举例1.插入2.插入3.插入动态表举例1.插入2.插入3.插入4.插入动态表举例溢出1.插入2.插入3.插入4.插入5.插入动态表举例溢出1.插入2.插入3.插入4.插入5.插入动态表举例1.插入2.插入3.插入4.插入5.插入动态表举例1.插入2.插入3.插入4.插入5.插入6.插入7.插入动态表举例考虑一连串n个插入。指向一个插入的最坏情况时间是Θ(n).因此,n个插入的最坏运行时间是n·Θ(n)=Θ(n2).错误!实际上,n个插入的最坏情况费用进行是Θ(n)≪Θ(n2).我们看看为什么是这样：最坏情况分析令ci=第i个插入的

3、代价如果i–1刚好是2的幂,其他.严格分析令ci=第i个插入的代价如果i–1刚好是2的幂,其他.严格分析n个插入的费用.因此,每个动态表操作的平均费用是Θ(n)/n=Θ(1).严格分析平摊分析是一种分析方法，证明在一系列操作中，每个操作的平均代价很小，即使在这个系列中一个操作的代价比较大。虽然我们进行平均，但是，其中并不涉及概率!•平摊分析保证在最坏情况下每个操作的平均性能。平摊分析三种常用的平摊分析方法：•聚集法,•记账法,•势能法.我们刚刚看到的是聚集分析。聚集法虽然简单，但是不如其他两种方法精确。特别是，记账法和势能法可以给每个操作分配特定的平摊代价。平摊分析的类

4、型•给第i个操作虚构一个平摊代价ĉi,1单位的工作付$1(比如时间).•执行操作消费一定的代价.•任何当时没有消费的余额存在银行准备给以后的操作使用。•银行的余额不能为负值!我们必须要保证对所有的n•这样,总的平摊代价提供了总的实际代价的上界。记账法例子:溢出假设给第i个插入操作平摊费用为ĉi=$3。•$1付给这次插入操作•$2给以后表倍增预存当表倍增的时候,$1付给移动一个最近加入的项,同时$1付给移动一个旧的项.动态表的记账分析假设给第i个插入操作平摊费用为ĉi=$3。•$1付给这次插入操作•$2给以后表倍增预存当表倍增的时候,$1付给移动一个最近的项,同时$1付给

5、移动一个旧的项.举例:溢出动态表的记账分析例子:假设给第i个插入操作平摊费用为ĉi=$3。•$1付给这次插入操作•$2给以后表倍增预存当表倍增的时候,$1付给移动一个最近的项,同时$1付给移动一个旧的项.动态表的记账分析键的不变量:存款余额不会低于0.这样,平摊代价的和给真实代价提供了一个上界。*第一个操作的代价仅仅是$2,不是$3.动态表的记账分析思路:将银行帐号视为动态集合的势能。框架:•开始时，初始的数据结构为D0.•操作i将Di–1转换为Di.•操作i的代价为ci.•定义势能函数Φ:{Di}→R,使得Φ(D0)=0并且对所有的i，Φ(Di)≥0.•平摊代价ĉi和

6、相关的Φ定义为ĉi=ci+Φ(Di)–Φ(Di–1).势能法势能ΔΦi•如果ΔΦi>0,那么ĉi>ci.操作i在数据结构中存储势能以备后用.•如果ΔΦi<0,那么ĉi

7、好是2的幂,其他;如果i–1刚好是2的幂,其他;平摊代价计算情况1:i–1刚好为2的幂。平摊代价计算情况1:i–1刚好为2的幂。平摊代价计算情况1:i–1刚好为2的幂。平摊代价计算情况1:i–1刚好为2的幂。平摊代价计算情况2:i–1不是2的幂。情况1:i–1刚好为2的幂。情况2:i–1不是2的幂。情况1:i–1刚好为2的幂。平摊代价计算情况2:i–1不是2的幂。情况1:i–1刚好为2的幂。平摊代价计算因此,n插入最坏情况的代价为Θ(n)。情况2:i–1不是2的幂。情况1:i–1刚好为2的幂。情况2:i–1不是2的幂。情况1:i–1刚好为