算法导论17.1-3_算法导论17.3-3

作者：花生_TL007 | 2024-04-07 01:09:10

踩

算法导论17.3-3

                    
                    问题描述 
 假定我们对一个数据结构执行一个由nn个操作组合成的操作序列，当ii严格为2的幂时，第ii个操作的代价为ii,否则代价为1。使用聚合分析确定每个操作的摊还代价。
问题求解 
 假设cici是第ii个操作的代价，则 
 
ci={ii是2的幂1其他ci={ii是2的幂1其他
 
nn个操作的代价是 
 
∑i=1nci≤n+∑j=0⌈lgn⌉n2j≤n+n+n2+n4+...+2+1=n+n−121−12=n+(2n−1)<3n∑i=1nci≤n+∑j=0⌈lgn⌉n2j≤n+n+n2+n4+...+2+1=n+n−121−12=n+(2n−1)<3n

 使用聚合分析确定每个操作的摊还代价为O(n)/n=O(1)O(n)/n=O(1)。在上面的求解过程中用到了等比数列前nn项和公式 
a11−qn1−q=a1−anq1−qa11−qn1−q=a1−anq1−q

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/花生_TL007/article/detail/375447