作者assassin88 (AI)
看板Grad-ProbAsk
標題Re: [理工] [algo]-求closed form
時間Mon Jan 4 11:29:35 2010
※ 引述《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
1F：推 doom8199:我的想法很單純，就是看 k(n) 的型態去猜它的 "特解" 01/04 18:27
2F：→ doom8199:會長的如何。 一開始的 (1) 式是中間想法 01/04 18:28
3F：→ doom8199:也就是去猜 a*log(n) 帶入 T(n) 可以滿足遞迴式 01/04 18:29
4F：→ doom8199:結果展開後發現無法與原遞迴式做比較係數 01/04 18:29
5F：→ doom8199:所以就重新假設 "特解" 的型態是 a*log(n) + b 01/04 18:30
6F：→ doom8199:然後再帶入。 若發現又不合，那就再重新假設 QQ 01/04 18:30
7F：→ doom8199:用解 ODE 的例子你會比較好懂y 01/04 18:32
8F：→ doom8199:假設 一ODE 為 y'' - 2y' + y = e^x 01/04 18:32
9F：→ doom8199:若你嘗試假設特解為 yp = ae^x , 帶入ODE後會發現不存在 01/04 18:33
10F：→ doom8199:a, 使得ODE的等號成立。 所以就改假設新的特解型態為 01/04 18:34
11F：→ doom8199:yp = axe^x + be^x , 結果發現可以解出 a、b 01/04 18:34
12F：推 doom8199:至於我所謂的 case by case , 是指 k(n) 01/04 18:37
13F：→ doom8199:例如 k(n) 有可能是 n*logn 、 n^2*(logn)^3、... 等 01/04 18:38
14F：→ doom8199:您想解 T(n) 的 closed form , 也只能先藉由已知 k(n) 01/04 18:39
15F：→ doom8199:然後嘗試去猜特解。想導出 general form 應該是不太可能 01/04 18:40
16F：→ doom8199:不然就不會有 divide and conquer 、 master thm. 這類的 01/04 18:41
17F：→ doom8199:概念出現。因為大問題解不出來，所以就先觀察小問題 01/04 18:42