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

[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值 囧
: 這個時間複雜度 要如何算出 謝~~

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 114.39.17.230
推 supergud:n-1沒有乘2 這樣對嗎
→ sodas2002:喔 算太快了 哭哭
→ sodas2002:要乘要乘 那用解遞迴的方式比較快
→ sodas2002:不過還是2^n~
推 supergud:是說用非齊次解嗎
→ sodas2002:嗯 不過看習慣啦 我自己是做遞迴比較快~
→ sodas2002:喝 來睏 明天台大網媒衝一發~