作者cschenptt (chen)
看板Grad-ProbAsk
标题[理工] 演算法 时间复杂度 Amotized cost
时间Fri Dec 28 01:26:02 2018
问题：
有一个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
https://i.imgur.com/ZsawILX.jpg
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.112.150.48
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1545931567.A.A53.html
※ 编辑: cschenptt (140.112.150.48), 12/28/2018 01:38:32
1F：→ JKLee: 请问n是prob. size吗? n是指所有的bit数量吗? 12/28 01:41
请问大大是问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
2F：→ Leaving: 应该是在问计算过程里面的n吧 12/28 08:47
3F：→ Leaving: 另外不是很清楚你计算第一行的式子怎麽来的@@ 12/28 08:48
4F：→ Leaving: 如果n指的是counter value, lg(1)前面乘的应该是n, 每次 12/28 08:54
5F：→ Leaving: 都会跳 12/28 08:54
6F：→ JKLee: 可否给原始的题目? 12/28 10:58