作者NOtWorThy ()
看板Grad-ProbAsk
标题[理工] [资结] master thm & extended master thm
时间Mon Nov 16 23:18:35 2009
问题1
为什麽形如
T(n) = aT(n/b) + n^logab * (logn)^k , k >= 1
不能直接用 Master thm
这不是可以用 case 1 吗?
ex.
T(n) = 2T(n/2) + nlogn
sol:
n^log2 2 = n = O(nlogn)
by case 1 不是可以解吗??
问题2
T(n) = 4T(n/2) + n^3
sol:
这题可以by case 3
但是要找 c s.t aT(n/b) <= cT(n)
这个c要怎麽找??
他找的c是1/2
烦请高手不吝赐教
谢谢!!!
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 122.116.218.120