Re: [理工] 時間複雜度
※ 引述《yuchiao0921 ()》之銘言：
: 某函式定義如下：
: int fun(int n)
: {
: if (n>1) return (fun (n/2)+n*n*n)
: else return (n*n)
: }
: 請問此函式之時間複雜度為何？
f(n)=f(n/2)+n^3
用master theorem即可
為O(n^3)
展開法我自己展開怪怪的(太久沒看書)
用解遞迴的方式解
f(n)=f(n/2)+n^3
令n=2^k
f(2^k)=f(2^k-1)+(2^k)^3
=f(2^k-1)+8^k 注:(2^k)^3 = 2^3k = 8^k
令Ak=f(2^k)
則遞迴式可寫成 Ak = A(k-1) + 8^k, A(1)=1
特徵多項式:b-1=0 則b=1
Ak(h) = C {齊次解}
令特解Ak(p) = d8^k 代入原式
可得d*8^k-d*8^(k-1) = 8^k
k=1時8d-d = 8 => d=8/7
Ak(p)=8/7*8^k
Ak = Ak(h)+Ak(p) = C + 8/7*8^k
遞入初始條件
A(1) = 1 = C + 8^2/7 => C = -57/7
Ak = -57/7 + 8/7*8^k
f(n) = Ak = -57/7 + 8/7*8^k = -57/7 + 8/7*n^3(最大項)
則為O(n^3)
有錯請指證,考完試後就沒算了,很可能算錯
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 116.59.254.85
※ 編輯: seal0112 來自: 116.59.254.85 (04/23 03:11)
→
04/23 03:46, , 1F
04/23 03:46, 1F
→
04/23 15:29, , 2F
04/23 15:29, 2F
※ 編輯: seal0112 來自: 116.59.232.224 (04/23 16:01)
推
04/25 13:48, , 3F
04/25 13:48, 3F
→
04/25 13:48, , 4F
04/25 13:48, 4F
樓上說的對,寫錯了...把數學函數跟時間函數搞錯
所以應該是
T(n)=T(n/2)+C (c為1次加法跟兩次乘法之cost)
case 2 of Master Method
T(n)=O(logn)
※ 編輯: seal0112 來自: 220.136.22.98 (04/25 23:41)
推
04/27 19:52, , 5F
04/27 19:52, 5F
討論串 (同標題文章)
