Re: [理工] [algo]-求closed form

[assassin88 (AI)]

※ 引述《doom8199 (～口卡口卡　修～)》之銘言：
: ※ 引述《assassin88 (AI)》之銘言：
: : T(n) = 2T(n/2) + lgn
: :      = 4T(n/4) + 3lgn - 2
: :      = ...
: :      = 2^kT(n/2^k) + (2^k-1)lgn + ???
: : 後面常數像求不出closed form..不知道該怎麼求..麻煩指導一下，感謝。
: ---
:     這類遞迴式我都用湊的 　＝.＝
:     型如  T(n) = aT(n/2) + k(n)  ,  a 屬於R
:     想法就是先設法湊成    [T(n) - f(n)] = a[T(n/2) - f(n/2)]  的型態
:     所以只要找出 f(n) , 就能解得  T(n)
:     可是若展開後比較係數, 會發現:
:     f(n) - af(n/2) = k(n)
:     這個式子剛好就是我們欲求的 XD
:     所以正常來說， T(n) 只能根據 k(n) 的型態
: 　　case by case 的去解它
      ^^^^^^^^^^^^
      指的是解遞迴的方式嗎(master, 迭代.....)
: ---
: 　　  T(n) = 2T(n/2) + log(n)    (令底為2)
:       不防先假設   T(n) + a*log(n) = 2*[ T(n/2) + a*log(n/2) ]   ___(1)

                     這裡呃假設是從原式來嗎？似乎跟原式不等..還是= =?
:                 → T(n) = 2T(n/2) + alog(n) - 2a
:       這時會發現比較係數後 a=1
:       但卻多了常數項 -2a = -2   , 無法消除
: 　　　所以就大膽假設 "特解" 也有常數項
:       即重令:   T(n) + a*log(n) + b = 2*[ T(n/2) + a*log(n/2) + b]
:              → T(n) = 2T(n/2) + alog(n) - 2a + b
:       比較係數後可知:  ┌  a = 1          →  ┌ a = 1
: 　　　　　　　　　　　 └  -2a + b = 0 　　　 └ b = 2
:       所以原式可改寫成:
:          T(n) + f(n) = 2*[T(n/2) + f(n/2)]      with  f(n) = log(n) + 2
: ----
:       有了上式，就能導出一般式:
:       不仿令  n = 2^r
:       所以  T(n) + f(n) = 2*[T(n/2) + f(n/2)]
:                         = 2^(r) * [T(1) + f(1)]
:                         = n[T(1) + 2]
:       即  T(n) = n[T(1) + 2] - f(n)
:                = T(1)*n + 2n-log(n) - 2


你的方法太高級了= ="
我果然數學太差....
請問這題還有一般的解法嗎(ˊˋ)？

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 118.160.180.110
推 doom8199:我的想法很單純，就是看 k(n) 的型態去猜它的 "特解"
→ doom8199:會長的如何。　一開始的 (1) 式是中間想法
→ doom8199:也就是去猜 a*log(n) 帶入 T(n) 可以滿足遞迴式
→ doom8199:結果展開後發現無法與原遞迴式做比較係數
→ doom8199:所以就重新假設 "特解" 的型態是 a*log(n) + b
→ doom8199:然後再帶入。　若發現又不合，那就再重新假設 QQ
→ doom8199:用解 ODE 的例子你會比較好懂y
→ doom8199:假設 一ODE 為 y'' - 2y' + y = e^x
→ doom8199:若你嘗試假設特解為  yp = ae^x , 帶入ODE後會發現不存在
→ doom8199:a, 使得ODE的等號成立。　所以就改假設新的特解型態為
→ doom8199:yp = axe^x + be^x , 結果發現可以解出 a、b
推 doom8199:至於我所謂的 case by case , 是指 k(n)
→ doom8199:例如 k(n) 有可能是 n*logn 、 n^2*(logn)^3、... 等
→ doom8199:您想解 T(n) 的 closed form , 也只能先藉由已知 k(n)
→ doom8199:然後嘗試去猜特解。想導出 general form 應該是不太可能
→ doom8199:不然就不會有 divide and conquer 、 master thm. 這類的
→ doom8199:概念出現。因為大問題解不出來，所以就先觀察小問題