作者cormen5566 (风行者)
看板Grad-ProbAsk
标题Re: [问题] complexity
时间Wed Apr 22 19:56:27 2009
※ 引述《bernachom (Terry)》之铭言：
: 请教一下
: T(n)约等於，T(n/2)+c,c为constant time for 乘法运算
: T(n)=O(logn)
: 可是..
: logn不是应该为1/1+1/2+...+1/n才是吗??
: 谢谢
1. T(n) = T(n/2) + c
2. 令 f(n) = c ,使得 T(n) = aT(n/b) + f(n)
3. lg(1) 0
因为 n = n = 1 = Theta(f(n))
by master method case 2可知
T(n) = Theta( f(n)*lg n )
= Theta( c * lg n )
= Theta( lg n ) → 因为c是常数
= O( lg n )
有错请鞭^^
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.229.77.39