时间复杂度与算法执行步数的关系及大n下复杂度优劣对比问题

• 算法的执行步数是输入规模为n时的精确运算量，通常可以表示为带常数系数、包含低阶项的表达式，比如你提到的20000n²、0.001n⁵就是忽略了低阶项的精确步数表达式。
• 时间复杂度是对执行步数的渐近抽象，它只关注n趋向于无穷大时执行步数的增长趋势，会直接忽略常数系数、低阶项，只保留主导项的阶数。比如上面两个步数对应的时间复杂度分别是O(n²)和O(n⁵)。

你的疑惑本质是没考虑到高阶多项式的增长速度会彻底碾压低阶多项式，常数系数的影响只在小n场景下生效。我们可以直接计算两个函数的交点来验证：
令两个步数相等：
20000n² = 0.001n⁵
两边除以n²（n>0时运算合法），可得：
n³ = 20000 / 0.001 = 2 * 10^7
计算可得交点约为n≈271，这是两个算法性能的临界值：

• 当n < 271时，0.001n⁵的数值更小，确实是后者耗时更少
• 当n > 271时，20000n²的数值更小，而且n越大，两者的差距会呈指数级拉开

举两个实际大n的例子：

1. n=1000时：
   20000n² = 2 * 10^10，0.001n⁵ = 1 * 10^12，后者耗时是前者的50倍
2. n=10000时：
   20000n² = 2 * 10^12，0.001n⁵ = 1 * 10^17，后者耗时已经是前者的50000倍

我们做时间复杂度分析的核心目的是评估算法在处理大规模输入时的性能表现，工业场景下的输入规模往往远大于271这个临界值，所以我们会直接认为O(n²)的算法比O(n⁵)的时间复杂度更优，不需要考虑常数系数的差异。

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