Re: [理工] [DS] 96成大資工
※ 引述《christianSK (AG)》之銘言：
: http://0rz.tw/RunXm
: alog的第二題
: 如果說用master theorem可以知道是 theta(N^2*N^0.5)
: 不過我展開之後卻發現有點奇怪
2 0.5
原題 T(N) = 4*T(N/2) + N *N
2 0.5
先算一個 T(N/2) = 4*T(N/4) +(N/2) *(N/2)
2 0.5 2 0.5
T(N) = 4( 4*T(N/4) +(N/2) *(N/2) ) + N *N
2 0.5 0.5
= 16T(N/4) + N *N [1 + (1/2) ]
= ...
2 2 0.5 0.5 0.5
= N T(1) + N *N [1 + (1/2) + ... + (1/2^(lgN-1)) ]
lgN
2 2 0.5 1 - sqrt(0.5)
= N T(1) + N *N [ --------------------]
1 - sqrt(0.5)
我展開長這樣, 不知道正確與否? 有算的人請幫忙check 謝謝!! ^^
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.43.195.103
※ 編輯: BenLinus 來自: 114.43.195.103 (02/11 23:15)
推
02/11 23:48, , 1F
02/11 23:48, 1F
→
02/11 23:51, , 2F
02/11 23:51, 2F
推
02/12 00:05, , 3F
02/12 00:05, 3F
→
02/12 00:06, , 4F
02/12 00:06, 4F
→
02/12 00:07, , 5F
02/12 00:07, 5F
推
02/12 00:10, , 6F
02/12 00:10, 6F
→
02/12 00:12, , 7F
02/12 00:12, 7F
討論串 (同標題文章)