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

看板Grad-ProbAsk作者 (sodas)時間16年前 (2010/02/26 23:06), 編輯推噓2(2推 0噓 5→)
留言7則, 2人參與, 最新討論串34/38 (看更多)
※ 引述《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
推
02/26 23:09, , 1F
n-1沒有乘2 這樣對嗎
02/26 23:09, 1F
→
02/26 23:14, , 2F
喔 算太快了 哭哭
02/26 23:14, 2F
→
02/26 23:14, , 3F
要乘要乘 那用解遞迴的方式比較快
02/26 23:14, 3F
→
02/26 23:16, , 4F
不過還是2^n~
02/26 23:16, 4F
推
02/26 23:20, , 5F
是說用非齊次解嗎
02/26 23:20, 5F
→
02/26 23:22, , 6F
嗯 不過看習慣啦 我自己是做遞迴比較快~
02/26 23:22, 6F
→
02/26 23:23, , 7F
喝 來睏 明天台大網媒衝一發~
02/26 23:23, 7F
‣ 更多 sodas2002 的文章
文章代碼(AID): #1BX-DVpc (Grad-ProbAsk)
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 34 之 38 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共38篇)
‣ 更多 sodas2002 的文章
文章代碼(AID): #1BX-DVpc (Grad-ProbAsk)