自做网站视频,网站内容百度不收录,fn网站不是做那么好吗,企业网站推广方法有哪些?摊还分析
1何为摊还分析#xff1f;
摊还分析主要求解数据结构维护序列执行的所有操作的平均时间#xff0c;来评价操作的代价#xff0c;从而保证最坏情况下每个操作的平均性能。
2聚合分析
2.1何为聚合分析#xff1f;
若长度为n的操作序列最坏情况下所花费时间为T(…摊还分析
1何为摊还分析
摊还分析主要求解数据结构维护序列执行的所有操作的平均时间来评价操作的代价从而保证最坏情况下每个操作的平均性能。
2聚合分析
2.1何为聚合分析
若长度为n的操作序列最坏情况下所花费时间为T(n)。
聚合分析状态下摊还代价CT(n)/n。
2.2栈的时间复杂度分析
此时栈有3个操作
1.PUSHS,x表示将对象x压入栈中。
2.POPS,x表示从栈顶弹出一个元素保证不会弹空。
3.MULTIPOPS,k表示弹出栈顶的k个元素保证不会弹空。
试证明单次操作的摊还代价。
一次POP的最坏时间是On的那么n个操作的时间是否是O(n^2)的呢 其实不然。
证明事实上每一个元素只入栈一次出栈一次而栈中最多存在n个元素所以n次操作最坏只需要O(n)的时间。而每个操作的摊还代价CO(n)/nO(1)。
2.3单调队列的时间复杂度分析
单调队列也有两个操作
1.PUSHque,x表示在队尾插入。
2.POPque,k表示在队首弹出k个元素保证不会弹空。
试证明单次操作的摊还代价。
证明每个元素依然只入队一次出队一次最多n个元素最坏为On每个操作的摊还代价CO(n)/nO(1)
3.核算法
3.1何为核算法
我们进行摊还分析时对每一个不同的操作赋予不同的费用将赋予一个操作的费用称为它的摊还代价。
每一次摊还代价超出实际代价时就可以将多出的部分“储存”起来称之为“信用”它在以后的操作中可以“抵账”。 但核算法应确保总摊还代价大于总真实代价的上界。如果用ci表示第i个操作的真实代价ĉi表示第i个操作的摊还代价要求 也就是 在保证信用非负的情况下总摊还代价是总真实代价的上界。 3.2栈的核算法分析
还是刚才栈的例子。
它的每个操作的实际代价为
PUSH 1
POP 1
MULTIPOP k
我们赋予每个操作这样的摊还代价 PUSH 2
POP 0
MULTIPOP 0
可证明对于任意的操作序列总摊还代价大于总实际代价。
就相当于每一次PUSH存入2元1元当做PUSH的代价还有1元当做将来弹出这个元素的代价。这样可以保证信用永远非负之前PUSH多付出的摊还代价预支了以后POP需要的代价。所以在POP是可以当作没有任何代价了。总摊还代价还是O(n)的。
3势能法
3.1何为势能法
势能法没有将预支代价表示为特定操作的信用而是表示为“势能”用势能的释放预支代价。势能与整个数据结构对象相关联而非像核算法一样和某个特定的操作代价相关联。
我们将一个初始数据结构D0执行n个操作。对于每一个操作i令ci为第i个操作的实际代价令Di为数据结构Di-1上执行第i个操作所得到的结果数据结构。势函数φ把每个数据结构表示为一个势能大小。 摊还代价ĉiciφDi-φDi-1
每个操作的摊还代价为实际代价势能变化。
总摊还代价 3.1.1
需要定义φ使得φ(Dn)φ(D0)那么总摊还代价会是总实际代价的上界因此我们要求φ(Di)φ(D0)一般把φ(D0)定义为0只需要保证φ(Di)0即可。
3.2栈的势能法分析
栈的操作同上。
我们设φ(Di)表示i次操作后栈中的元素数量s。
D0初始为空栈。φ(D0)初始为0.
1.对于PUSHS,xφ(Di)-φ(Di-1)(s1)-s1。由公式3.1.1可得ĉiciφ(Di)-φ(Di-1)112
2.对于MULTIPOPS,kφ(Di)-φ(Di-1)(s-k)-s-k。由公式3.1.1可得ĉiciφ(Di)-φ(Di-1)k-k0
同理POP的摊还代价也为0.
综上所述每个操作的摊还代价均为O1因此总摊还代价为On此时必有φ(Di)φ(D0)。
4.动态表扩张
你需要完成对一个序列的插入快速查询操作。
简单来说就是实现C中的vector为其寻找一个空间为On的方法。
对于这个问题我们的方法是每次空间存满扩展两倍空间并复制原来空间的内容进入新的空间。
1.若使用聚合分析
ci
1.当i-12^kcii
2.当i-1!2^kci1
总代价为 2.若通过核算法。
令每一次操作的ĉi3。总摊还时间为3n。
3.若通过势能法。
定义φ(Di)2*T.num-T.size。
1.非扩张
ĉiciφ(Di)-φ(Di-1) 12*numi-sizei-2*numi-1-sizei-1 12*numi-sizei-2(numi-1)-sizei 3
2.扩张 ĉiciφ(Di)-φ(Di-1) numi2*numi - sizei-2*numi-1 - sizei-1 numi2*numi-2*numi -1-2*numi -1-numi -1 numi2numi - 1 3
总摊还代价为O(n)。
5.思考
如何求堆的摊还代价
如何求AVL的摊还代价
如何求splay的摊还代价
6.参考文献
算法导论
