作者FRAXIS (喔喔)
看板Grad-ProbAsk
标题Re: [理工] [资结]-递回问题
时间Tue Dec 29 20:54:20 2009
※ 引述《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
1F：推 pigbo:看不懂XD 12/30 12:30
2F：推 pigbo:看懂了XD 12/30 16:10
3F：推 sevenpu:感谢^___^ 01/01 15:20