关于Big O表示法的两个面试复杂度问题求证

让我们直接把这两个问题掰明白，核心是回到Big O符号的严格定义——这是判断所有这类问题的唯一标准，别凭直觉瞎猜：

问题1：40ⁿ 是否属于 O(2ⁿ)？ #

结论：完全不属于

你之前的错误在于混淆了“多项式中的常数系数”和“指数的底数”——Big O忽略的是多项式项前面的固定常数因子，但指数的底数是决定增长速度的核心变量，完全不能忽略。

根据Big O的严格数学定义：如果存在常数 ( C > 0 ) 和 ( n_0 \geq 0 )，使得对于所有 ( n \geq n_0 )，都有 ( |f(n)| \leq C \cdot g(n) )，那么我们说 ( f(n) \in O(g(n)) )。

把 ( f(n)=40^n ) 和 ( g(n)=2^n ) 代入定义：
[
40^n = (2 \times 20)^n = 2^n \times 20^n
]
要满足 ( 2^n \times 20^n \leq C \times 2^n )，两边同时除以正数 ( 2^n )，得到 ( 20^n \leq C )。但 ( 20^n ) 会随着n的增大无限趋近于无穷大，不可能存在一个固定的常数C能永远“罩住”它。因此，40ⁿ绝对不属于O(2ⁿ)。

问题2：(40n)² 是否属于 O(n²)？ #

结论：完全属于

你之前的直觉有误——这里的常数是多项式项的系数，而Big O的设计初衷就是忽略这种固定不变的常数因子。

先展开式子：
[
(40n)^2 = 40^2 \times n^2 = 1600n^2
]
套用Big O定义：我们取 ( C=1600 )，( n_0=1 )，那么对于所有 ( n \geq 1 )，显然有 ( 1600n^2 \leq 1600 \times n^2 )，完全满足定义的要求。不管n多大，左边永远是右边的1600倍，这个倍数是固定的，不会随着n变大而增长，所以(40n)²属于O(n²)。

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