Re: [理工] [資結]-成大97-資工程式設計

看板Grad-ProbAsk作者IDontBite (IDontBite)時間16年前 (2010/02/06 13:10)推噓3(3推 0噓 1→)

留言4則, 3人參與討論串2/3 (看更多)

※ 引述《shinhwabo (.....)》之銘言： Solving the recurrence T(n)=2T(└√n┘)+㏒n using big-O notation as tight as possible 求板上的高手幫忙解答 thx Assume T(1) = O(1) T(n) = 2T(n^1/2) + logn = 2{2T(n^1/4) + log(n^1/2)} + logn = 4T(n^1/4) + 2*(1/2)logn + logn = 4T(n^1/4) + 2logn = (2^k)T(n^(1/2^k)) + klogn ----(a) //拍謝, 剛剛導錯, 以下修正 T(2) = 2T(1) + log2 = O(1) 則令 n^(1/2^k) = 2 得 k = loglogn T(n) = logn*T(2) + (loglogn)(logn) = O(loglogn * logn) -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 58.114.130.207 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.32.189.59

推

FRAXIS

02/06 13:35, , 1^F

02/06 13:35, 1^F

※ 編輯: IDontBite 來自: 114.32.189.59 (02/06 13:52)

推

JMD

02/06 23:24, , 2^F

02/06 23:24, 2^F

→

JMD

02/06 23:35, , 3^F