推 pigbo:看不懂XD 12/30 12:30
推 pigbo:看懂了XD 12/30 16:10
推 sevenpu:感謝^___^ 01/01 15:20
※ 引述《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