[理工] [資結] 時間複雜度

看板Grad-ProbAsk作者 (小阮)時間15年前 (2010/08/25 21:41), 編輯推噓2(2推 0噓 9→)
留言11則, 4人參與, 7年前最新討論串6/9 (看更多)
問題真是越看越多ˊ ˋ 1. 求Θ T(0)=0 T(1)=1 T(n) = 5T(n-1)-6T(n-2) 2. 求Θ T(n) = 1^4 + 2^4 + 3^4 +... + n^4 3. 求Θ T(n) = T(n/4) + T(3n/4) +n 再次感謝^^ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.40.82.208
推
08/25 21:51, , 1F
第三題畫樹 或套用某定理1/4 + 3/4 = 1 => Θ(nlogn)
08/25 21:51, 1F
→
08/25 22:09, , 2F
不懂..想知道解法
08/25 22:09, 2F
→
08/25 22:16, , 3F
用推文補充問一個 O(2^n) 和 O(n^logn) 的大小
08/25 22:16, 3F
→
08/25 22:17, , 4F
答案給後面的比較大 但怎麼算都相反= =
08/25 22:17, 4F
推
08/25 23:30, , 5F
第一題可以用離散的特徵方程式法來解...令an=T(n),an=Ax^n
08/25 23:30, 5F
→
08/25 23:32, , 6F
解得x=2,3 =>an=c0(2)^n+d0(3)^n 把條件帶入解未定係數
08/25 23:32, 6F
→
08/25 23:36, , 7F
第二題Σi^k=Θ(i^(k+1)) 不然也可列成n(n^4+1)/2
08/25 23:36, 7F
→
08/25 23:37, , 8F
（首項+末項）*項數/2..會得(n^5+n)/2= Θ(n^5)
08/25 23:37, 8F
→
08/25 23:48, , 9F
第三提要用遞迴樹分析...或直接用其倒出來的公式..
08/25 23:48, 9F
→
08/25 23:51, , 10F
T(n)=Σ(k-i+1)!/i!(P^(k-i)q^in)+cnΣ(p+q)^i
08/25 23:51, 10F
→
12/15 00:23, 7年前 , 11F
第二題Σi^k=Θ(i https://noxiv.com
12/15 00:23, 11F
‣ 更多 juan19283746 的文章
文章代碼(AID): #1CTHsCvb (Grad-ProbAsk)
討論串 (同標題文章)
完整討論串 (本文為第 6 之 9 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共9篇)
‣ 更多 juan19283746 的文章
文章代碼(AID): #1CTHsCvb (Grad-ProbAsk)