この
T(n) = 2T( n/2 ) + n lg n再帰方程式のマスター定理を解くことができますか? 私は、3ree ケース条件のいずれも満たさないため、ここでマスター定理を適用できないと彼が述べているリンクから来ています。一方、彼は別の例
T(n) = 27T(n/3) + Θ(n^3 lg n) を取り上げ、閉じた解を見つけましたtheta(n^3logn) 。これを解決するために、マスター定理の 2 番目のケースを使用If f(n) = Θ(nlogba (lg n)k ) then T(n) ∈ Θ(nlogba (lg n)k+1) for some k >= 0 しました。ここで、2 番目のケースに完全に適合するのに、ここで 2 番目のケースを適用できないのはなぜでしょうか。
私の考え: a = 2 , b =2; let k =1 then f(n) = theta(n^log_2 2 logn) for k= 1 so T(n) = theta(nlogn) しかし、彼がこれについて述べたように、マスター定理を適用することはできません。 .
注: これは inおよび in の f(n) bcz によるものです* * ここで間違っている場合は訂正してください。T(n) = 2T( n/2 ) + n lg n f(n) = nlog nT(n) = 27T(n/3) + Θ(n^3 lg n)f(n) = theta(n^3log n)