1

再帰関係を解決する方法についていくつか問題があります。

T(n) = T(n/2) + log2(n)、T(1) = 1、n は 2 の累乗

これは宿題なので、ただ答えを教えてはいけません。問題をどのように開始するのか疑問に思っていました。

クラスでは、マスター定理について説明しました。しかし、それがこの特定の関係を解決する最善の方法だとは思いません。

問題を開始する方法がよくわかりません... ただ行くべきですか

T(n) = T(n/2) + log_base2(n)
T(n/2) = [T(n/4)+log_base2(n/2)]
  T(n) = [T(n/4)+log_base2(n/2)] + log_base2(n)

そして、私が見ることができる何かを得るために私の道を進み続けて、基本的な方程式を作りますか?

4

4 に答える 4

0

これはマスター定理で解決できます。あなたa=1と. b=2_ f(n) = log(n)それからc = log2(1) = 0。あなたcとf(n)あなたのせいで、2番目のケース（どこで）に陥りますk=1。

したがって、解はΘ(log 2 n)

于 2015-12-15T08:29:01.487 に答える