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

看板Grad-ProbAsk作者 (あれはいらないからでち)時間6年前 (2017/11/24 00:36), 6年前編輯推噓2(2推 0噓 0→)
留言2則, 2人參與, 6年前最新討論串2/2 (看更多)
※ 引述《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
推
11/24 01:34, 6年前 , 1F
感謝g大！！原來還有這種方法
11/24 01:34, 1F
推
11/24 11:47, 6年前 , 2F
這方法猛
11/24 11:47, 2F
‣ 更多 gouya 的文章
文章代碼(AID): #1Q5lZwyP (Grad-ProbAsk)
‣ 更多 gouya 的文章
文章代碼(AID): #1Q5lZwyP (Grad-ProbAsk)