推 NOtWorThy:第一我說錯 那不可以用CASE 3嗎 第2 WHY F(N)=N^3?? 11/17 18:24
→ NOtWorThy:THX 你的解答!! 11/17 18:24
※ 引述《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