[理工] 關於時間複雜度

看板Grad-ProbAsk作者 (粥有兪)時間12年前 (2013/10/14 23:37), 編輯推噓2(2推 0噓 6→)
留言8則, 3人參與, 最新討論串1/1
其實明天要交作業了(誤) http://ppt.cc/xCtN 上面那題沒什麼想法... 遞迴樹感覺有點可行 我猜是 Θ(n^2*logn) 下面那題 好像也找不太到反例，感覺是True -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.118.235.143
推
10/14 23:52, , 1F
應該是 n^3 (1+3/2+(3/2)^2....(3/2)^k)*n^2
10/14 23:52, 1F
→
10/14 23:54, , 2F
k是樹高 被n/3和2n/3 bound住 k取log(n)
10/14 23:54, 2F
→
10/14 23:56, , 3F
等比級數 ((3/2)^(k+1)-1)/(3/2-1)*n^2 看成
10/14 23:56, 3F
→
10/14 23:58, , 4F
(3/2)^log(n)*n^2 ~ n^3
10/14 23:58, 4F
→
10/15 00:33, , 5F
sorry 我的想法應該是錯的
10/15 00:33, 5F
→
10/15 00:49, , 6F
><
10/15 00:49, 6F
→
10/15 01:29, , 7F
只能代 Akra-Bazzi 了 解出來是 n^2
10/15 01:29, 7F
推
10/15 02:31, , 8F
第一題我猜是n^2 第二題有限制fi是正數或是遞增嘛？
10/15 02:31, 8F
‣ 更多 s97610017 的文章
文章代碼(AID): #1IN0-yoB (Grad-ProbAsk)