再例：计数器 ·实际代价 ·置1：1；置0：1 ·摊还代价 ·置1：2 ·置0：0 ·核算过程： ·每一次置1，除了用掉1元代价后，一定留下1元代价，供置0使用 ·摊还总代价一定高于实际总代价：至少有一个1存在（有1元盈余) ·结论： 将计数器从0递增到n,最多是n个increase?操作，On),实际总代价的上再例：计数器 • 实际代价： • 置1：1；置0：1 • 摊还代价： • 置1：2 • 置0: 0 • 核算过程： • 每一次置1，除了用掉1元代价后，一定留下1元代价，供置0使用 • 摊还总代价一定高于实际总代价：至少有一个1存在（有1元盈余） • 结论： • 将计数器从0递增到n，最多是n个increase操作，O(n)，实际总代价的上 界