O(N(logN)^4)的时间复杂度增长速度是否快于O(N^3)？

结论 #

O(N(logN)⁴) 的增长速度远慢于 O(N³) #

推导逻辑 #

判断两个大O阶的高低，核心是看N趋近于无穷大时两个函数的比值极限：

• 计算比值 f(N) = N(logN)⁴ / N³ = (logN)⁴ / N²
• 对f(N)求N→∞的极限，连续应用4次洛必达法则后，分子会变为常数，分母仍为N的正次幂，最终极限值为0

极限为0就说明当N足够大时，分子的增长速度远低于分母，也就是O(N(logN)⁴)的增长阶低于O(N³)。 #

直观数值验证 #

我们可以代入实际的大N数值看差异（默认log以2为底）：

• N=1024时：(log₂1024)⁴=10⁴=10000，N(logN)⁴=1024*10000≈1e7；N³≈1e9，后者是前者的100倍
• N=10⁶时：(log₂10⁶)≈20，(logN)⁴=1.6e5，N(logN)⁴≈1e6*1.6e5=1.6e11；N³=1e18，后者是前者的600多万倍

注：对数的底数不影响最终结论，不同底数的对数仅相差常数系数，会被大O表示法忽略。

通用规律 #

只要对数项的指数是固定常数，不管多大，任何带对数幂的线性/亚线性项，增长速度都会慢于任意指数>1的多项式项。

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