漸近分析の質問に問題があります:私の質問は、質問に記載されているように「a」の場合に最大値を計算することです:
An Algorith A has running time T(n)= 7T(n/2) + n^2
and Algorith B has running time T' = aT'(n/4) + n^2.
What will be the maximum integer value of 'a' such that algorith B runs
asymptotically faster than A.
これでアルゴリズムの概念のみを使用する必要がある場合、または他の方法で解決する場合は、「a」の値をどのように見つける必要がありますか。
これは、マスター定理を使用するのに最適な場所です。
最初の再帰では、T(n) = 7T(n/2) + n 2、マスター定理は次のように述べています。
log b a = log 2 7 は d = 2 よりも大きいため、再帰は T(n) = Θ(n log 2 7 ) になります。
ここで、T'(n) を見てみましょう。ここで、未知数、b = 4、および d = 2 があります。次の条件が当てはまる場合:
次に、マスター定理は、T'(n) = Θ(n log 4 a ) = o(n log 2 7 ) と言い、これで完了です。したがって、a について解く必要があります。
これを行うと
ログ4 a < ログ2 7
log 2 a / log 2 4 < log 2 7 (ログの基本式の変更を使用)
ログ2 a / 2 < ログ2 7
ログ2 a < 2 ログ2 7
log 2 a < log 2 7 2 (ログの電力規則を使用)
ログ2 a < ログ2 49
a < 49
したがって、選択できる最大の積分 a は 48 です。
お役に立てれば！
方程式を解いて、非再帰的なランタイム式を取得します