complexity-theory - なぜlog(n)! ゼロじゃない？

Question

その log(n) を証明してみます! log(n!) よりも速く成長しています

なぜlog(n)! n∈N に対してゼロではありません。

log(1) はゼロだと思っているので、結果を掛けた後の数字はすべてゼロになります。

前もって感謝します。

Answer 1

log(n!)次の理由により、ゼロではありません。

log(m * n) == log(m) + log(n)
log(2!) = log(2 * 1) = log(2) + log(1) = log(2) + 0

という点ではlog(n)!、その部分は無視できますlog(1)。たとえば、ルートが 1 つのノードを持つ二分探索木を考えてみましょう。二分探索木を使用した値の検索はlog(n)、n がノードの数である場合です。したがって、ルートのみを使用すると、実行する計算によると検索はゼロになるはずですが、ルートの値を確認する必要があるため、それでも 1 です。この意味でlog(1) == 1、混乱を避けるために仮定することができます。