动态表数据结构摊销分析

证明对于动态表,如果每次达到容量时,大小都从n每次增加到n +√n,则为Θ(n ^ 3/2),其中n是元素数?如何解决此类问题?使用聚集分析形成方程很复杂

评论
pporro
pporro

这种构造的动态表是Θ(sqrt(n))。

Most (sqrt(n) per cycle) pushes take Θ(1) constant time. The last push per cycle takes Θ(n) time to reallocate. Because sqrt(n)+1=Θ(sqrt(n)) operations have occurred in this cycle, the amortized cost is ( sqrt(n)Θ(1) + Θ(n) ) / Θ(sqrt(n)) = Θ(sqrt(n)).

点赞
评论