温馨提示:本文翻译自stackoverflow.com,查看原文请点击:algorithm - Show 2^n is O(n!)

algorithm - 显示2 ^ n是O(n!)

发布于 2020-03-29 22:06:05

我正在努力理解为什么它们相等。帮助将不胜感激。我试过说2 ^ n意味着倍增n倍,但是我不确定这与阶乘相似。

查看更多

提问者
StrugglingStudent202
被浏览
98
trincot 2020-01-31 19:02

为了证明2 ñO(N!) 你需要证明2 ñ ≤·M·N!,对于一些常数中号和的所有值Ñ≥Ç,其中Ç也是一些常数。

因此,让我们选择M = 2C = 1

对于n = C,我们看到2 n = 2并且M·n!= 2,所以确实在碱情况下,2 Ñ ≤·M·N!是真的。

假设它对某些n(≥C)成立,是否对n + 1也成立是的,因为如果2 ñ ≤·M·N!那么2 n + 1≤M·(n + 1)!

左侧乘以2,而右侧乘以至少 2。

因此,这证明通过感应是2 ñ ≤·M·N!对于所有n≥C,对于MC的选定值结果2 nO(n!)