推 FRAXIS:時間複雜度: T(n) = 2T(n/2) + O(1) 11/23 19:21
→ polomoss:請問為何是2倍?? 雖然我也覺得4倍不合理，因為不收斂 11/23 21:17
推 abien:aT(n/b)+c, a表問題個數, n/b表問題資料量, c表問題成本 11/23 23:51
→ abien:這邊只有兩個T(n/2), 而if else的成本為O(1)=>1 11/23 23:52
begin
if n<=1 then
return 2
else
return (2 * recursive(n/2) + 2 * recursive(n/2))
end
請問列成遞迴式是什麼~? 感覺書上給的答案怪怪的
還有求出的 theta 是多少~?
謝
--
┌這篇文章讓您覺得？─────────────────────────────┐
│ │
│ 一"一 \ / >\\\< ╯ ╰ ∩ ∩ ▁ ▁ ＞＿＜ ㄧ ㄧ+ │
│ 皿 ε □ ▽ ▇Δ ▇ ╰╯ ╯ │
│ 北七 亂喔 害羞 莎笅 爽啦 哭爸 ＸＤ 科科 │
└──────────────────────────────────────┘
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.116.14.2