Re: [理工] [資結]-master thm & extended master thm
※ 引述《FRAXIS (喔喔)》之銘言：
: ※ 引述《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) 所以不適用
Case 3的條件其中有一個是
f(n) = Ω(n^(log_b a + e)) for some e > 0
題目中
f(n) = n log n 和 n^(log_b a + e) = n^(1+e)相比
又 log n = o(n^e) != Ω(n^e) for all e > 0，所以條件永遠不會成立
另外一個問題，你的f(n)和T(n)的定義好像沒搞清楚..
Master Theorem可以套用的形式是
T(n) = aT(n/b) + f(n)
所以f(n)才會是n^3
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.119.162.50
※ 編輯: FRAXIS 來自: 140.119.162.50 (11/17 21:28)
推
11/18 11:41, , 1F
11/18 11:41, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 3 之 3 篇)：