作者FRAXIS (喔喔)
看板Grad-ProbAsk
标题Re: [理工] [资结]-master thm & extended master thm
时间Tue Nov 17 15:36:09 2009
※ 引述《NOtWorThy ()》之铭言：
: 问题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 不是可以解吗??
Case 1的条件
f(n) = O(n^(log_a b - e)) for some constant e > 0
f(n) = nlogn != O(n^(log_2 2)) = O(n) 所以不适用
: 问题2
: T(n) = 4T(n/2) + n^3
: sol:
: 这题可以by case 3
: 但是要找 c s.t aT(n/b) <= cT(n)
: 这个c要怎麽找??
: 他找的c是1/2
: 烦请高手不吝赐教
: 谢谢!!!
Case 3的条件
af(n/b) <= cf(n) for some constant c < 1 and sufficient large n
f(n) = n^3
4 * (n/2)^3 = n^3 / 2, 所以 c 可以找1/2
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.119.162.50
1F：推 NOtWorThy:第一我说错 那不可以用CASE 3吗 第2 WHY F(N)=N^3?? 11/17 18:24
2F：→ NOtWorThy:THX 你的解答!! 11/17 18:24