math - D-ary ヒープの実行時間?

Question

d-Ary ヒープの実行時間を O(log _d n) から O( (log n) / (log d)) に単純化するにはどうすればよいですか?

正しい単純化は次のようになります: log _d n = log d * log n

除算の単純化はどのように導出されますか?

Answer 1

これは共通の恒等式を使用して対数の底を変換します。

logx(z) = logm(z) / logm(x)

両辺に log _m (x) を掛けると、次のようになります。

logm(z) = logx(z) * logm(x)

これは、サイトの質問の回答に相当します。

詳細については、こちらをご覧ください。

Answer 2

仮定する

x = ログd (n)

同等に、

n = d ×

それで

log 2 n = log 2 (d x ) = x log 2 (d)

log ₂ (d)で割ると、次のようになります。

log 2 (n) / log 2 (d) = x

など

log 2 (n) / log 2 (d) = x = log d (n)

もちろん、dが固定されていると仮定すると、log ₂ (d) は単なる定数です。など

O( log d (n) ) = O( 1 / log 2 (d) * log 2 (n) ) = O( log 2 (n) )

つまり、Big-Oh 表記に関する限り、任意の (1 より大きい) 対数の底を他の (そのような) 対数の底に変更できます。したがって、ベースを削除して O( log(n) ) と書くのが通例です。