Re: [理工] [資結]-時間複雜度
看板Grad-ProbAsk作者Lautreamont (Maldoror is dead)時間16年前 (2010/02/26 23:24)推噓1(1推 0噓 0→)留言1則, 1人參與討論串35/38 (看更多)
※ 引述《sodas2002 (sodas)》之銘言：
: ※ 引述《cocaincola (☆★)》之銘言：
: : 請問一下
: : T(n)=2*T(n-1)+n
: T(n)=2T(n-1)+n
: =2( 2T(n-2)+n-1 ) +n
: =4T(n-2)+n+(n-1)
: =8T(n-3)+n+(n-1)+(n-2)
: =2^K*T(n-k)+n+(n-1)+(n-2)+...+(n-k+1)
: =2^n*T(0)+n+(n-1)+(n-2)+...+1
: =2^n+n(n+1)/2=O(2^n)
: : 本來想套在
: : Master theorem 上 卻發現 沒有b值 囧
: : 這個時間複雜度 要如何算出 謝~~
T(n) = 2^n*T(0)+n+2(n-1)+2^2(n-2)+...+2^(n-1)
let S = n+2(n-1)+2^2(n-2)+...+2^(n-1)
2S = 2n+2^2(n-1)+2^3(n-2)+...+2^(n-1)*2+2^n
2S-S = -n + [2+2^2+2^3+...+2^n] = -n + 2^(n+1)-2
所以還是O(2^n)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.160.178.245
※ 編輯: Lautreamont 來自: 118.160.178.245 (02/26 23:26)
※ 編輯: Lautreamont 來自: 118.160.178.245 (02/26 23:26)
推
02/26 23:27, , 1F
02/26 23:27, 1F
討論串 (同標題文章)