[理工] 演算法 時間複雜度 Amotized cost
問題：
有一個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時
------
我算出來
amotrized cost 是O(lg(n)lg(n))
worst case 也是O(lg(n)lg(n))
amotrized 沒有比 worst case少
請問是否是算錯了?
附上amotized cost的計算過程
https://i.imgur.com/j5hAn5k.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.150.48
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1545931567.A.A53.html
※ 編輯: cschenptt (140.112.150.48), 12/28/2018 01:38:32
→
12/28 01:41,
5年前
, 1F
12/28 01:41, 1F
請問大大是問lgn的n嗎？
是的話 n是指 該bit的值
eg. 10 = 1010
第二個bit=1 代表2 -> n=2 -> lg(2)
第四個bit=1 代表8 -> n=8 -> lg(8)
bit=0 -> 不理
所以對10做A操作 時間複雜度是 lg2+lg8
※ 編輯: cschenptt (140.112.150.48), 12/28/2018 01:57:43
→
12/28 08:47,
5年前
, 2F
12/28 08:47, 2F
→
12/28 08:48,
5年前
, 3F
12/28 08:48, 3F
→
12/28 08:54,
5年前
, 4F
12/28 08:54, 4F
→
12/28 08:54,
5年前
, 5F
12/28 08:54, 5F
→
12/28 10:58,
5年前
, 6F
12/28 10:58, 6F