算法复杂度疑问：O(2^n)与O(n!)哪个对应的算法运行速度更快？

嘿，这个问题问得特别戳中复杂度分析的一个关键点——很多刚入门的同学都会对这两个指数级/阶乘级的增长速度犯迷糊。直接给结论：**O(2^{n)对应的算法运行速度比O(n!)的快得多**，准确来说，n!的增长速度是远远碾压2}n的，随着n的增大，两者的差距会夸张到无法想象。

咱们拿具体的数值来直观感受下：

• 当n=10时：2^10=1024，而10!=3628800，后者是前者的3000多倍
• 当n=20时：2^{20≈104万，20!≈2.43×10}18，这差距已经是天文数字级别的了
• 再往上n=30，2^{30≈10亿，30!更是达到了2.65×10}32，完全不在一个量级

从数学角度看，我们可以对比两者的比值：n! / 2^n，当n趋向于无穷大时，这个比值会趋近于无穷大——这就意味着n!的增长速度比2^{n快得不是一点半点。换句话说，同样处理规模为n的问题，O(n!)的算法需要执行的操作数会以远超O(2}n)的速度爆炸式增长。

举个实际的例子：O(2^{n)的典型场景比如枚举一个集合的所有子集，n=20的时候还能勉强跑出来；但O(n!)的典型场景比如旅行商问题的暴力枚举所有路径，n=12就已经要处理479001600条路径，n=15的话直接就到1.3×10}12，普通电脑根本跑不动。

内容的提问来源于stack exchange，提问作者Integrity