問題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