我试图了解摊销的复杂性并在网上进行了几次搜索，但我还找不到好的资源。
那么任何人都可以解释什么是摊销复杂性以及它如何在每次操作的展开树中变成 O(lg n) 吗？
user1787584
问问题
1958 次
1 回答
1
在展开树上执行的任何操作，无论是插入删除..等，成本都由展开操作决定。因此仅考虑展开操作的成本，即在要展开的节点上执行的旋转。
The amortized function is given by a=c+3Rfinal(v)-3Rinitial(v)
其中 a 是摊销成本，c 是实际成本，Rfinal 是展开操作后的排名，Rinitial 是旋转前节点的排名。（任何节点的排名由其子树的高度给出，即 log|S|其中 S 是其下的节点数）
现在考虑最坏的情况，其中节点要展开，是叶子，因此它的初始排名由 0 给出。在展开到顶部后，即作为根节点，它的排名变为 log n，其中 n 是树中的节点总数.
a<= 2+3logn-0
O(logn).
于 2013-11-01T18:52:21.657 回答