マスター定理はいつ実際に適用できますか？

Question

私はこれにかなり不満です。 CLRS第3版で

、95ページ（章4.5）、それは違い

f(n)/n^(log_b(a)) = (n lg n)/n^1 = lg n

があるので

T(n) = 2T(n/2) + n lg n

などの再発がマスター定理では解決できないことに言及します多項式ではありません。

しかし、私はthisのようなページを見ることができます。ページの下部には、まったく同じ再発が記述されており、「拡張ケース2」にも入るのでマスター定理で解くことができます違いは非多項式です。 のログ係数を1つ増やしてn lg^2 nになります。

その後、私はthis場所の例では（e）のようなページに渡って来るが（再発がT(n) = 4T(n/2) + n^2 lg nある）拡張ケース2の明確なアプリケーションのように思えるが、その後、解決策はn^2 log^2 nではなく、むしろn^2 log n！間違っているのですか、または間違っていますか？

矛盾を明確にして、マスター定理を使用できるときとできないときを正確に分かりやすくできますか？いつ多項式差分チェックが重要ですか？それはいつですか？拡張ケース2は使用可能か、それとも実際に何か違反していますか？

EDIT：

私が直接、2枚目の用紙から再発（e）を解決しようと、私が手：

T(n) = n^2 lg^2(n)/2 + n^2 lg(n)/2

はこの大きなないシータn^2 lg^2 nですか？

Answer 1

本はCase 3を使用して解決することはできないと述べている：

適切なフォームを持っているように見えるにもかかわらず：...あなたは間違っているケース3は

---

を適用すべきであると思うかもしれません

しかし、この定理は、マスター定理、ケース2を使用して解くことができます。

T(n) = 2T(n/2) + nlgn: 

は、我々は定義：

a = 2, b = 2, f(n) = nlgn 

Master theorem case 2を使用する：

c = log_2(2) = 1 
k = 1 

そしてf(n)はTheta(nlogn)に確かです。

ので、マスター定理ケース2へのすべての条件が適用され、私たちは推測することができます。

T(n)がTheta(n^c * log(n)^(k+1)) = Theta(n*log(n)^2)

---

長い話に短いです

、マスターの定理は3例があります。それぞれのケースには適用する前提条件があります。ケース3には、コンバージェンスが必要なため、より複雑な前提条件があります。
ケース3の前提条件はこの式には適用されないため、ケース3は使用できません。ケース2の前提条件が適用され、使用できます。