Re: [理工] [資結]-時間複雜度

[Lautreamont (Maldoror is dead)]

※ 引述《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)
推 sodas2002:哦 好方法~