商务网站建设sz886,想接网站自己做,数码产品网站建设,l辽宁建设工程信息网算法导论【摊还分析】—聚合分析、核算法、势能法聚合分析核算法势能法假定我们对一个数据结构执行一个由 n 个操作组成的操作序列#xff0c;当 i 严格为 2 的幂时#xff0c;第 i 个操作的代价为 i#xff0c;否则代价为 1 聚合分析
总共有n个操作#xff0c;1,2,4.....…
算法导论【摊还分析】—聚合分析、核算法、势能法聚合分析核算法势能法假定我们对一个数据结构执行一个由 n 个操作组成的操作序列当 i 严格为 2 的幂时第 i 个操作的代价为 i否则代价为 1 聚合分析
总共有n个操作1,2,4.....,2⌊lgn⌋1,2,4.....,2^{⌊\lg n⌋}1,2,4.....,2⌊lgn⌋其中有至多k⌈lgn⌉k⌈\lg n⌉k⌈lgn⌉个操作序号为2的幂则 S∑k0⌊lgn⌋2k(n−⌈lgn⌉)∗11∗(1−2⌊lgn⌋1)1−2n−⌈lgn⌉2⌊lgn⌋1−1n−⌈lgn⌉≤3n−⌈lgn⌉−1O(n)\begin{aligned} S\sum_{k0}^{⌊\lg n⌋}2^k(n-⌈\lg n⌉)*1\\ \cfrac{1*(1-2^{⌊\lg n⌋1})}{1-2}n-⌈\lg n⌉\\ 2^{⌊\lg n⌋1}-1n-⌈\lg n⌉\\ \le3n-⌈\lg n⌉-1\\ O(n) \end{aligned} Sk0∑⌊lgn⌋2k(n−⌈lgn⌉)∗11−21∗(1−2⌊lgn⌋1)n−⌈lgn⌉2⌊lgn⌋1−1n−⌈lgn⌉≤3n−⌈lgn⌉−1O(n) 所以每个操作的摊还时间代价为O(n)nO(1)\cfrac{O(n)}{n}O(1)nO(n)O(1)
核算法
设每个操作的代价都为333 第2k−11到第2k−12^{k-1}1到第2^{k}-12k−11到第2k−1个操作为非2的幂多付的代价为2∗(2k−1−1−11)2k−22*(2^{k-1}-1-11)2^k-22∗(2k−1−1−11)2k−2在第2k2^k2k个次操作付的代价为333则可以用于支付第2k2^k2k次操作的信用为2k−232k12k2^k-232^k12^k2k−232k12k大于第2k2^k2k次操作应该付的代价故每个操作的摊还代价为O(1)O(1)O(1)
势能法
设势函数为 Φ(D0)0Φ(Di)2(i−2lg⌊i⌋)\Phi (D_0) 0\\ \Phi(D_i) 2(i-2^{\lg⌊i⌋})\\ Φ(D0)0Φ(Di)2(i−2lg⌊i⌋)
当i为2的幂时2⌊lgi⌋i,⌊lg(i−1)⌋1⌊lgi⌋2^{⌊\lg i⌋}i,⌊\lg (i-1)⌋1⌊\lg i⌋2⌊lgi⌋i,⌊lg(i−1)⌋1⌊lgi⌋ c^iciΦ(Di)−Φ(Di−1)i2(i−2⌊lgi⌋)−2(i−1−2⌊lgi−1⌋)i2i−2i2−2⌊lgi⌋12⌊lgi⌋1i−i−2⌊lgi⌋2⌊lgi⌋122\begin{aligned} \hat c_ic_i\Phi(D_i)-\Phi(D_{i-1})\\ i2(i-2^{⌊\lg i⌋})- 2(i-1-2^{⌊\lg i-1⌋})\\ i2i-2i2-2^{⌊\lg i⌋1}2^{⌊\lg i⌋1}\\ i-i-2^{⌊\lg i⌋}2^{⌊\lg i⌋1}2\\ 2 \end{aligned} c^iciΦ(Di)−Φ(Di−1)i2(i−2⌊lgi⌋)−2(i−1−2⌊lgi−1⌋)i2i−2i2−2⌊lgi⌋12⌊lgi⌋1i−i−2⌊lgi⌋2⌊lgi⌋122当i不为2的幂时2⌊lg(i−1)⌋2⌊lgi⌋2^{⌊\lg (i-1)⌋}2^{⌊\lg i⌋}2⌊lg(i−1)⌋2⌊lgi⌋ c^iciΦ(Di)−Φ(Di−1)12(i−2⌊lgi⌋)−2(i−1−2⌊lgi−1⌋)12i−2i2−2(2⌊lgi⌋−2⌊lgi−1⌋)123\begin{aligned} \hat c_ic_i\Phi(D_i)-\Phi(D_{i-1})\\ 12(i-2^{⌊\lg i⌋})- 2(i-1-2^{⌊\lg i-1⌋})\\ 12i-2i2-2(2^{⌊\lg i⌋}-2^{⌊\lg i-1⌋})\\ 12\\ 3 \end{aligned} c^iciΦ(Di)−Φ(Di−1)12(i−2⌊lgi⌋)−2(i−1−2⌊lgi−1⌋)12i−2i2−2(2⌊lgi⌋−2⌊lgi−1⌋)123 故每个操作摊还复杂度为O(1)O(1)O(1)
