比较 O((logn)!) 和 O(2^n)
Comparing O((logn)!) and O(2^n)
我很难比较这两个函数，
(登录)!
和
2^n
有什么好的数学证明吗？
可以很容易地证明，对于足够大的 n，它认为：
log(n)! <= log(n)^{log(n)} <= n^{log(n)} = 2^{log^2(n)}
我们现在只能考虑 2^n 和上面的表达式中 2 的指数 - n 和 log^2(n)（我们可以这样做，因为我们只考虑足够大 n 并且 2^x 对于正 x 是严格上升的）。证明下面的极限发散就足以证明 log(n)! 实际上是 o(2^n):
lim[n -> inf] (n)/(log^2(n))
现在我们应用 L'Hospital 规则：
= lim [n -> inf] `n/(2log(n))`
再一次：
= lim [n -> inf] `n/(2)`
向无穷大发散。
您无法比较 O((logn)!) 和 O(2^n)，因为 big O notation represents a set. O(g(n)) is the set of of all function f such that f does not grows faster than g, formally is the same is saying that there exists C and n0 such that we have |f(n)| <= C|g(n)| for every n >= n0. The expression f(n) = O(g(n)) is a shorthand for saying that f(n) is in the set O(g(n)). what we can do is check if 2^n=O((logn)!) or (log n)!=O(2^n) (note that it could be that both are not true). Luckily, if we use the Stirling approximation 我们知道
log((logn)!) = (logn)*(log (logn)) - logn + O(log(log n)) = O(n*(log 2))
因为 n * cost 比 (logn)*(log (logn)) 增长得更快，并且 (logn)*(log (logn)) 是 (logn)*(log (logn)) - logn + O(log(log n)) 中的前导项。所以我们得到 log((logn)!) = O(log(2^n)) 等同于 (log n)! = O(2^n)
我很难比较这两个函数，
(登录)!
和
2^n
有什么好的数学证明吗？
可以很容易地证明，对于足够大的 n，它认为：
log(n)! <= log(n)^{log(n)} <= n^{log(n)} = 2^{log^2(n)}
我们现在只能考虑 2^n 和上面的表达式中 2 的指数 - n 和 log^2(n)（我们可以这样做，因为我们只考虑足够大 n 并且 2^x 对于正 x 是严格上升的）。证明下面的极限发散就足以证明 log(n)! 实际上是 o(2^n):
lim[n -> inf] (n)/(log^2(n))
现在我们应用 L'Hospital 规则：
= lim [n -> inf] `n/(2log(n))`
再一次：
= lim [n -> inf] `n/(2)`
向无穷大发散。
您无法比较 O((logn)!) 和 O(2^n)，因为 big O notation represents a set. O(g(n)) is the set of of all function f such that f does not grows faster than g, formally is the same is saying that there exists C and n0 such that we have |f(n)| <= C|g(n)| for every n >= n0. The expression f(n) = O(g(n)) is a shorthand for saying that f(n) is in the set O(g(n)). what we can do is check if 2^n=O((logn)!) or (log n)!=O(2^n) (note that it could be that both are not true). Luckily, if we use the Stirling approximation 我们知道
log((logn)!) = (logn)*(log (logn)) - logn + O(log(log n)) = O(n*(log 2))
因为 n * cost 比 (logn)*(log (logn)) 增长得更快，并且 (logn)*(log (logn)) 是 (logn)*(log (logn)) - logn + O(log(log n)) 中的前导项。所以我们得到 log((logn)!) = O(log(2^n)) 等同于 (log n)! = O(2^n)