algorithm - マスター定理の一般化を使用した方程式の解

Question

証明がどのように機能するかを説明するのに助けを求めます。例を見たことがありますが、理解するのに苦労しています。

以下を証明せよ

方程式の解

T(n) = aT(n/b) + Θ(n ^k log ^p n) ここで、a ≥ 1、b > 1、p ≥ 0

• T(n) = O(n ^{log _b a} ) if a > b ^k

• T(n) = O(n ^k log ^p+1 n) a = b ^kの場合

• T(n) = O(n ^k log ^p (n)) if a < b ^k

これは、より良い形式の質問のスクリーンショットです

これはマスター定理の一般化です。

Answer 1

ある x =log(n)/log(b) の場合、n=b ^xになります。^{方程式をx}で割る

T(b ^x )/a ^x = T(b ^x-1 )/a ^x-1 + Θ((b ^k /a) ^x ·x ^p ·log ^p b)

m < x に対する項 m ^p ·q ^mの総和は次のとおりです。

• q < 1 の定数によって制限される
• q = 1 に対してx ^p+1のように成長する
• q > 1 の場合、最後の項 x ^p ·q ^xによって支配される

q=b ^k /a を認識して代入すると、結果が得られます

• a < b ^kの場合: T(b ^x )=O(a ^x )、または T(n)=O(n ^{log _b a} )
• a = b ^kの場合: T(b ^x )=O(x ^p+1 ·a ^x )、または T(n)=O(n ^{log _b a} ·log ^p+1 n )
• a > b ^kの場合: T(b ^x )=O(x ^p ·b ^kx )、または T(n)=O(n ^k ·log ^p n)