マスター定理はT(n) = aT(n/b) + f(n)、a >=1 および b > 1 の形式の再帰式で使用されます。この場合、b の値は再帰式から簡単に確認できますが、次の形式の再帰式があります。
T(n) = T((n/4)+3) + f(n)
どうすれば b を取得できますか?
1 に答える
0
したがって、再帰を単純化しようとすると、次のようになります。 T(n)= T((n+12)/3)) + f(n)
毎回 n を追加するものがあるため、2 つの可能性があります。方程式が T(n)=aT(n/b)+ f(n) の形式ではないためマスター定理が適用されないか、無視できます。 +12 は定数であり、n が変化しても変化しないため、T(n)= T(n/3)+f(n) と書き換えて、マスター定理でこれを解くと、答えが見つかります。上の方も同じである可能性が高いです。
または、再帰ツリーを使用してソリューションを簡単に推測できます
于 2016-10-01T12:54:56.223 に答える