Re: [理工] [資結]-遞迴問題
※ 引述《sevenpu (pu)》之銘言：
: n-1
: t(n) >= 2 Σ t(i) + n , t(1) >= 1
: i=i
: 怎麼求時間複雜度?
: 希望能用資管的角度來解答
: 感謝回答^^
我不知道怎麼解 t(n) >= 的形式.. 如果是 = 的話
n-2
t(n-1) = 2 Σ t(i) + n-1
i=1
t(n) - t(n-1) = 2 t(n-1) + 1
t(n) = 3t(n-1) + 1
所以應該就是 O(3^n)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.119.162.50
推
12/30 12:30, , 1F
12/30 12:30, 1F
推
12/30 16:10, , 2F
12/30 16:10, 2F
推
01/01 15:20, , 3F
01/01 15:20, 3F
討論串 (同標題文章)