如何求解给定两个函数的Big O（大O表示法）上界

大O刻画的是n趋近于无穷大时函数的渐近上界，推导时只需要遵循两个最核心的规则：

• 忽略所有常数系数、常数项
• 只保留增长速度最快的最高阶项，所有低阶项在n足够大时对增长趋势的影响可以忽略

先记牢不同类型函数的增长速度排序（从慢到快）：
常数阶 < 对数阶 < 多项式阶（即固定指数的幂函数，比如n、n²、n¹⁰⁰⁰） < 指数阶（即固定底数>1、n在指数位的函数，比如1.01ⁿ、2ⁿ、10ⁿ）
注意：只要是底数大于1的指数函数，无论底数多接近1，最终增长速度一定会超过任意固定次数的多项式函数，这是很多初学者容易搞错的点。

两个给定函数的具体推导 #

第一个函数 f(n) = n³ + 100n² + 5ⁿ #

拆分三项的增长级别：

• 100n²是二次多项式，系数100不影响阶数，属于低阶项
• n³是三次多项式，比二次项阶高，但仍属于多项式阶
• 5ⁿ是底数为5的指数阶，增长级别远高于多项式阶
  取最高阶项，最终大O表示法为 O(5ⁿ)

第二个函数 f(n) = n³ + 100n² + 1.1ⁿ #

拆分三项的增长级别：

• 前两项和第一个函数一致，最高为三次多项式n³
• 1.1ⁿ虽然底数只有1.1，看起来前期增长很慢，但它本质还是底数>1的指数函数，当n足够大时，增长速度会彻底碾压n³。举个直观的数值对比：n=100时1.1ⁿ≈13780，还小于n³=1e6；n=1000时1.1ⁿ≈2.47e41，而n³只有1e9，差距达到32个数量级，多项式项的影响已经可以完全忽略。
  取最高阶项，最终大O表示法为 O(1.1ⁿ)

验证小技巧：判断两个项谁的阶更高，可以求n趋近无穷时两项比值的极限，如果极限是0，说明分子是低阶项；如果极限是无穷大，说明分子是高阶项；如果极限是常数，说明二者同阶。

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