algorithm - この漸化式にマスターの定理を使用できますか？

Question

宿題の問題を解決し、再帰ツリーを使用しました。

しかし、解は、この漸化式はマスターの定理によって解くことができると言っています！

T（N）= 49T（N / 25）+ n ^（3/2）log（n）

n ^（3/2）log ^ 2（n）を解きました

しかし、解決策はn ^（3/2）log（n）と言いました

この場合がマスターの定理を使用できる理由がわかりませんが、それは正しいです。

Answer 1

a=49私たちはそれを見ることができますb=25。それに注意してlog_b(a) ~ 1.2ください3/2 = 1.5。したがって、log_b(a) < 3/2。したがって、f(n) = n^{3/2}log(n) = Omega(n^{log_b(a) + epsilon})いくつかのイプシロンについては、マスター定理のケース3が適用されることがわかります。したがって、実行時間は

T(n) = Theta(f(n)) = n^{3/2}log(n)

注：また、それを確認する必要があります

af(n/b) <= cf(n)

いくつかの定数のためにc。もちろん

49 (n/25)^{3/2} log(n/25) <= c n^{3/2}log(n)

これは、両側を除算し、両側からn^{3/2}減算することで確認できます。c log(n)

(49/25^{3/2} - c) log n - 49/25^{3/2} log(25) <= 0

これは確かに少なくともc > 49/25^{3/2}（これをきつくする必要はありません）に当てはまります。