[理工] [Algo]Substitution method
有些遞迴樹類型的題目，
猜出解後，利用substitution method證明時都寫得很卡，
不確定自己寫的夠不夠嚴謹，怕在這種基本題上丟掉分數，
比較大的問題在於取n0時不太知道該怎麼寫，
以下是我的證明過程，麻煩大家幫忙糾正.討論，thx!
ex: T(n) = T(n/3)+T(2n/3)+n
pf: To prove T(n) = O(nlog n) ,
i.e. exist positive constant c,n0 s.t. T(n)<=cnlog n,for all n>=n0
T(1) = T(0)+T(0)+1 = 1 <= c．1．log 1不可能找到c使之成立
T(2) = T(0)+T(1)+2 = 3 <= c．2．log 2當c>=2時成立
T(3) = T(1)+T(1)+3 = 5 <= c．3．log 3當c>=2時成立
T(4) = T(1)+T(2)+4 = 8 <= c．4．log 4當c>=2時成立
T(5) = T(1)+T(3)+5 = 11 <= c．5．log 5當c>=2時成立
T(6) = T(2)+T(4)+6 = 17 <= c．6．log 6當c>=2時成立
(這邊先猜n0=6,但還沒算出c值不確定n0是否會變不知道該不該在這寫n0=6)
Induction Hypothesis:假設6<=k<n時存在c使得T(k)<=cklog k成立
當k=n時 T(n) = T(n/3)+T(2n/3)+n
<= (cn/3)log n/3+(2cn/3)log 2n/3 +n
= (cn/3)(log n-log 3)+(2cn/3)(log n-log 3/2)+n
= cnlog n + n -(cn/3)log 3 - (2cn/3)log 3/2
<= cnlog n (取c=3)
by induction,取n0=6,c=3,T(n) = O(nlog n)得證
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.228.109.152
※ 文章網址: http://www.ptt.cc/bbs/Grad-ProbAsk/M.1420292041.A.0C1.html
→
01/03 21:58, , 1F
01/03 21:58, 1F
修正n0=2 -> n0=6,因T(n/3)在n<6不成立
※ 編輯: galapous (36.228.109.152), 01/03/2015 22:34:02