algorithm - 指数成本二进制计数器的摊销时间成本

Question

如果二进制计数器花费 O(2^i) 时间来更改第 i 位的值，那么 n 次增量操作的总成本的上限是多少？

Answer 1

假设您从零开始计数器，那么

• n 次操作改变 1 位（成本 O(n)），
• n/2 次操作改变 2 位（成本 O(n)），
• n/4 次操作改变了 4 位（成本 O(n)），
• ...

这意味着成本的界限是 O(n) 乘以计数器中的总位数，即 O(log n)，因为 n 位数需要 O(log n) 位。因此，总时间复杂度为 O(n log n)，因此每个操作的摊销成本为 O(log n)。