問題タブ [master-theorem]

マスター定理はT(n) = aT(n/b) + f(n)、a >=1 および b > 1 の形式の再帰式で使用されます。この場合、b の値は再帰式から簡単に確認できますが、次の形式の再帰式があります。

どうすれば b を取得できますか?

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

以下を証明せよ

方程式の解

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

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

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