Re: [課業] 資料結構/時間複雜度

作者: lovefo (lovefo) 看板: Examination
標題: Re: [課業] 資料結構/時間複雜度
時間: Sat Mar 27 23:13:53 2010

※ 引述《zadpos (人生啊)》之銘言：
: 1.考試科目：資料結構
: 2.章節名稱or篇名(單元關鍵字)：
: 3.目前參考用書or考古題出處：
: 4.想問的內容：求T(n)=T(n-1)+n的時間複雜度
: 5.想法：
: 我用代入法算出來是O(n^2) 答案應該也是O(n^2)
: 但如果用非齊次式算 r=1(二重根)
: 所以an=(c1*n+c2)1^n 那就是O(n)
: 是我哪裡有錯嗎??

因為 T(n)遞迴是非齊次

  齊次解 令法 T(n) = (c1)1^n
非齊次解 令法 T(n) = (d1 + d2*n + d3*n^2)

T(n) = (c1)1^n + (d1 + d2*n + d3*n^2)

     所以複雜度是 O(n^2)