complexity-theory - 为什么是日志（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)部分。以一棵二叉搜索树为例，它有一个节点，它的根。使用二叉搜索树搜索值是log(n)其中 n 是节点数。因此，根据您所做的计算，只有一个根，搜索应该为零，但它仍然是一，因为您必须检查根值。从这个意义上说，您可以假设log(1) == 1避免混淆。

Answer 2

您不应该计算n等于某个常数的表达式。为了证明函数f比函数增长得快g，你需要证明对于n无穷大， 的值f将大于 的值g。