作者polomoss (小泽)
看板Grad-ProbAsk
标题[理工] [资结]-复杂度
时间Mon Nov 23 18:24:13 2009
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
1F：推 FRAXIS:时间复杂度: T(n) = 2T(n/2) + O(1) 11/23 19:21
2F：→ polomoss:请问为何是2倍?? 虽然我也觉得4倍不合理，因为不收敛 11/23 21:17
3F：推 abien:aT(n/b)+c, a表问题个数, n/b表问题资料量, c表问题成本 11/23 23:51
4F：→ abien:这边只有两个T(n/2), 而if else的成本为O(1)=>1 11/23 23:52