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

作者: MarcusWill (天下第二控衛) 站內: Examination
標題: Re: [課業] 資料結構/時間複雜度
時間: Sun Mar 28 17:47:35 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-1)+n
我改寫成我習慣的代號
An-An-1=n

再令An=r^n
r-1=0  r=1 (只有一個根)

An^(h)=C1(1)^n
An^(p)=n (d0+d1*n)=d0n+d1n^2
代回原式
(d0n+d1n^2) - (d0(n-1)+d1(n-1)^2) = n
3d1n-d1+d0=n

d1=1/3  d0=1/3

An=C1+1/3(n)+1/3(n)^2

沒有初始條件不知道算出來對不對
不過我想你應該是在非齊次那邊算錯了
因為根是1所以An^p令法要多乘一個n在括號外面

bbs上好難解釋
不過遞迴解法我也只是背下來而以，沒有很懂真實意義