--

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.113.141.151 ※ 编辑: doom8199 来自: 140.113.141.151 (01/08 01:33) 赚一下 p 币XD 假设 T(n) = a*T(n/b) + f(n) 若想把上式改写成 T(n) - k(n) = a[T(n/b) - k(n/b)] 那得去 try k(n) 的型态 其实要分两个 case 讨论: <1> 直接由 f(n) 型态下去 try: ex: T(n) = 3T(n/4) + nlogn 因为要合并成 T(n) - k(n) = 3[T(n/4) - k(n/4)] 所以就同时考虑 k(n) 、 k(n/4) 也就是假设 k(n) 可由 nlogn 、 (n/4)log(n/4) 组成 这时若把 (n/4)log(n/4) 稍微整理一下 会得到 (n/4)log(n) - (n/2) 此时会发现 k(n) "也必须要有 n 这个项" 这时我们在重新假设: k(n) 可由 nlogn 、 (n/4)log(n/4) 、 n 、 (n/4) 组成 相当於 k(n) 可以由 nlogn 、 n 组成 到这步就等於可以 try k(n) = a*nlogn + b*n <2> 由 (logn)^r*f(n) 型态下去 try: (其中 r属於R) ex: T(n) = 2T(n/2) + n 这种 case 比较讨厌 因为若直接照第一种 case 的流程去想 会变成: 假设 k(n) 型态可由 n 、 (n/2) 组成 表示可以直接假设 k(n) = a*n 可是当带回原式: T(n) + a*n = 2[T(n/2) + a*(n/2)] → T(n) = 2T(n/2) → GG ---- 第二种 case 会爆的原因其实很简单 由 T(n) = 2T(n/2) 可解出通解 T(n) = T(1)*n 会发现 特解的型态跟齐性解相冲 有学工数的人应该对这句话再熟悉不过XD 若假设的 特解型态 和 齐性解 有重叠 我们会如何去修正特解的假设方式 ? O.D.E. 的处理方式， 跟解递回式完全一样 ! 就是改假设新的特解为 k(n)' = (logn)*k(n) ps: 可以想想为何要乘上 (logn)^r 来修正 ---- 回到 case 2 的 example 假设 k(n) = a*nlogn 则: T(n) + a*nlogn = 2[T(n/2) + a*(n/2)log(n/2)] → T(n) = 2T(n/2) + an 比较系数後可得 a = 1 即特解为 k(n) = nlogn ------------------------------------------------------------------------------ 其实 master theorem 本身就是一种 try 解的方式 只是演算法相对上比较重视最高 order 那个项 所以就没有像我这样直接把通解都求出来XD 若我们假设 T(n) = a*T(n/b) + f(n) 其通解为 T(n) = T(1)*T(n)_c + T(n)_p ^^^^^^ ^^^^^^ 齐性解 特解 master theorem 它是直接比较 T(n)_c 、 T(n)_p 、 f(n) 这三者的 order 所以才会分那麽多 case XD ( 会比较 f(n) 是因为想判断有没有和齐性解的型态重叠 ) 算是题外话 OTZ --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.113.141.151