Re: [理工] 幾題時間複雜度求算

[gouya (あれはいらないからでち)]

※ 引述《nO25948 (chenyuyan)》之銘言：
: https://i.imgur.com/AxNMAcO.jpg

T(n)=T(1)+...+T(n-2)+T(n-1)+n

T(n-1)=T(1)+...+T(n-2)+n-1

令T(n)=an

an=2an-1  +1 ....(*)

a1=T(1)=1

用離散的特徵方程式解

an(h)=c*2^n

an(p)=d  代回（*） d=-1

an=c*2^n  -1

a1=1  所以  c=1

an=2^n   -1  =T(n)


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.8.51.197
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1511454970.A.F19.html
※ 編輯: gouya (101.8.51.197), 11/24/2017 00:41:52
推 nO25948: 感謝g大！！原來還有這種方法
推 kssdpp222: 這方法猛