Re: [理工] 時間複雜度

[seal0112 ()]

※ 引述《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)
→ seal0112:如果有人疊代法疊出來麻煩教一下，我自己疊不出來
→ chunhsiang:怪怪的感覺...
※ 編輯: seal0112        來自: 116.59.232.224       (04/23 16:01)
推 jfurseteidce:O(logn)吧@@?  n*n*n 計算時間為const
→ jfurseteidce:時間上只算f(n/2)的部分
樓上說的對,寫錯了...把數學函數跟時間函數搞錯
所以應該是
     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)
推 chunhsiang:正解~