作者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