[理工] 台大103,成大102 103 演算法複雜度計算

看板Grad-ProbAsk作者h04mp6286 (H28)時間11年前 (2015/01/28 16:56)推噓7(7推 0噓 6→)

留言13則, 8人參與討論串1/1

台大103的第1題的第2小題 T(n) = T(n/2 + √n) + n 這題我真的沒有想法,用recursion-tree弄出一大推奇奇怪怪的東西成大102的計算題的第1小題 T(n) = 2T(n/2) + n/lgn 這題我看T○B的名校攻略上寫是O(nlglgn) 想請問是怎麼來的我已經知道每層是n/(-i+lgn)了要怎麼把n/(-i+lgn)化成O(nlglgn)啊還有成大103第2題想跟大家對下我寫:若M極大:T(n)=M :O(1) M極小:T(n)=16T(n/2)+Θ(1) :O(n^4) 可是感覺有點怪怪的,想參考神人們的寫法看看 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.239.110.239 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1422435383.A.9A1.html

推

kather

01/28 17:00, , 1^F

01/28 17:00, 1^F

→

kather

01/28 17:02, , 2^F

01/28 17:02, 2^F

推

drink1004

01/28 18:56, , 3^F

01/28 18:56, 3^F