[理工] [演算法] 證明

看板Grad-ProbAsk作者時間15年前 (2010/07/23 21:27), 編輯推噓0(0推 0噓 0→)
留言0則, 0人參與, 最新討論串1/2 (看更多)
如何證明 T(n) = 2T( |_n/2_| + 17 ) + n 的複雜度 O(n*log n) ? 我的想法: 1. Guess T(n) = O(n*log n) then Assume T(n)<= c * nlog n 2. 代入原式得 T(n) <= 2*c* (|_n/2_| + 17)*log( |_n/2_| + 17 ) + n = c*(n+34)log( |_n/2_| + 17 ) + n 接下來不會了..... -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 220.136.215.97
‣ 更多 suspect1 的文章
文章代碼(AID): #1CIPYhHq (Grad-ProbAsk)
‣ 更多 suspect1 的文章
文章代碼(AID): #1CIPYhHq (Grad-ProbAsk)