推 suspect1:謝謝解答 07/24 07:33
如何證明 T(n) = 2T( |_n/2_| + 17 ) + n 的複雜度 O(n*log n) ?
1.用Master Theorem
T（n）= A* T(n/b) + g(n) , 用n^logb^(A) --->這個是log以b為底..
去和g（n）比較
其中A＝2 b=2 g(n)=n，而n^log2^(2)＝ n = g(n)
--->符合老大定理的若 g(n)= O(n^logb^(A)(logn)^k),
則T(n) = O(n^logb^(A)(logn)^(k+1))
故T（n）= O(nlogn）得證
2.可以試試看轉換的方式
假設 n ＝ 2^k => T(2^k) = 2T(|_2^k-1_| + 17) + 2^k
這裡|_2^k-1_|的級數會大於17，所以在求Big-O時，17可以省略
令Ak ＝ T(2^k) => Ak ＝ 2A（k-1） + 2^k
移項 ＝>Ak - 2A（k-1） = 2^k
然後去求齊次解...經過一連串離散非齊次解的運算...答案就出來了同1.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.116.0.100
※ 編輯: tureday 來自: 122.116.0.100 (07/24 03:04)