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

Question

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

Answer 1

假设你从零开始计数器，那么<​​/p>

• 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)。