大O表示法中为何8^n属于O(2^n)？求解1/3*8^n-10的复杂度

你这里首先是记混了Big O的判定规则：8ⁿ 完全不属于 O(2ⁿ) 量级，这是初学渐近复杂度时非常容易踩的误区，本质是把对数、多项式、指数三类函数的缩放规则搞串了。

Big O的核心判定标准 #

先把最根本的定义摆出来，所有归类都要符合这个规则，不用死记硬背各种特例：

若要判定 f(n) = O(g(n))，必须能找到两个固定的正实数：常数c、阈值n₀，使得所有满足 n ≥ n₀ 的输入，都符合 0 ≤ f(n) ≤ c·g(n)。
简单说就是：当n足够大之后，f(n)的增长速度永远不会超过g(n)乘以一个固定常数。

为什么8ⁿ不能归为O(2ⁿ) #

很多人会错把“常数因子不影响Big O归类”的规则套到指数底数上，这个规则只适用于乘在整个项外侧的常数：

• 比如5*2ⁿ、0.1*2ⁿ都可以归为O(2ⁿ)，只要分别取c=5、c=0.1就能满足上面的定义。
• 但底数位置的常数不能直接忽略，对指数函数做恒等变形就能看明白：
  8ⁿ = (2³)ⁿ = 2^(3n)
  如果你硬要说它是O(2ⁿ)，代入定义就需要满足2^(3n) ≤ c*2ⁿ，化简后得到4ⁿ ≤ c——左边会随着n增大无限增长，根本不可能被一个固定的常数c管住，因此这个上界完全不成立。

习题 f(n) = 1/3 * 8ⁿ - 10 的推导过程 #

按定义走三步就能出结果：

1. 当n足够大时（这里算一下就能知道n≥2时，1/3*8ⁿ≈21.3，已经比减去的10大很多），低阶项、常数项对增长趋势的影响可以忽略，因为它们不会改变指数项的增长速度。
2. 式子中主导增长的项是1/3 *8ⁿ，乘在外侧的常数系数1/3不影响Big O归类，直接取c=1/3、n₀=2就能满足定义要求。
3. 最终这个表达式的时间复杂度是O(8ⁿ)，也可以等价写成O(2^(3n))，但绝对不能简化成O(2ⁿ)。

容易混淆的规则提醒 #

别把对数的规则乱套到指数上：

• 对数类复杂度因为有换底公式：log_b n = (1/log_2 b) * log_2 n，换底带来的是固定常数系数，所以不管底数是多少，对数复杂度统一归为O(log n)。
• 指数类的底数变化会直接改变增长的“量级”，底数越大，增长速度快的程度是指数级拉开的，绝对不能随便换底等价。

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