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

[IDontBite (IDontBite)]

※ 引述《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:T(2)變成O(log n)的理由是甚麼？
※ 編輯: IDontBite       來自: 114.32.189.59        (02/06 13:52)
推 JMD:給樓上  因為2^loglogn=logn
→ JMD:求出k=loglogn之後 T(n)=2^loglogn+(loglogn)(logn)
推 honey0024:T(2) = 2T(1) + log2 = O(1) 請問這個式子是代入原式嗎