作者bernachom (Terry)
看板Grad-ProbAsk
标题[问题] complexity
时间Wed Apr 22 02:19:20 2009
请教一下
T(n)约等於，T(n/2)+c,c为constant time for 乘法运算
T(n)=O(logn)
可是..
logn不是应该为1/1+1/2+...+1/n才是吗??
谢谢
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.228.99.191
1F：→ s336:你一直递回带进去 最後T(n)=T(1)+clog(n)=O(log n) 04/22 09:46
2F：→ s336:1/1+1/2+...+1/n这是用harmonic去夹挤所求出约等於log n 04/22 09:50
3F：→ s336:T(n)=T(n/2)+c=T(n/4)+2c=.....=T(n/2^i)+ic n/2^i=1 04/22 10:08
4F：→ s336:求出i=log n 代入=>T(n)=T(1)+clog n 令T(1)=0 04/22 10:10
5F：→ bernachom:原来是这样，谢谢您^^ 04/22 10:27
6F：→ ssccg:我觉得你对big-O的定义不太清楚，T(n) = O(logn) 04/22 20:52
7F：→ ssccg:不代表T(n)的值等於logn，而是growth rate小於等於logn 04/22 20:53
8F：→ bernachom:清楚了，谢谢您 04/24 23:28