問題：
有一個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時