问题：
有一个binary counter
给予某一种操作A
A操作的时间复杂度是O(lgn)
n代表的是
当bit为1时 所在的位置的值
例如 对101做A操作
第一个bit是1 -> n=2^0=1 -> O(lg(1))
第二个bit是0 -> 不理
第三个bit是1 -> n=2^2=4 -> O(lg(4))
所以"一次A操作"时间复杂度是 O(lg(1))+0+O(lg(4))
1. A操作amotized cost
我的方法是对binary counter 从1加到n (每次+1)
也就是1=001做一次A操作,2=010做一次,3=011做一次....n做一次
最后再除n
2. A操作的worst case
我认为worst case应是 0111111...1 也就是n=2的次方-1时
作者: Leaving 2018-12-28 08:47:00
应该是在问计算过程里面的n吧另外不是很清楚你计算第一行的式子怎么来的@@如果n指的是counter value, lg(1)前面乘的应该是n, 每次都会跳