algorithm - マスターメソッド - 分析

Question

これはアルゴリズムの分析に関するものです。たとえば、問題の実行時間は次のとおりです。

T(n) = { 1, for n == 1 | T(n/3) + THETA(1), for n > 1}

さて、これはTHETA(log base3 n)

しかし、Master Method を使用するとTHETA(log base2 n)、Case II を使用してに評価されます。

マスターメソッドから正しい答えを得るにはどうすればよいですか?

Answer 1

彼らは同じです。任意の 2 つの塩基aおよびbについては、通常、塩基についてはまったく言及せず、 とだけ言います。Θ(loga n) = Θ(logb n)Θ(log n)

これは、 に対して定数である係数だけ異なるためです。loga n = (1 / logb a) * logb n1 / logb an