算法分析中的增长率排序：按渐近增长率对指定函数排序

咱们先直接给出最终的排序结果（增长率从慢到快），之后再逐个拆解每个函数的渐近复杂度，帮你理清背后的逻辑：

• 2^10（常数阶，O(1)）
• 2^logn、3n+100logn、4n（均为线性阶，O(n)）
• nlogn、4nlogn+2n（均为线性对数阶，O(nlogn)）
• n^2 + 10n（平方阶，O(n²)）
• n^3（立方阶，O(n³)）
• 2^n（指数阶，O(2ⁿ)）

详细拆解每个函数的复杂度级别 #

常数阶：2^10 #

2^10就是固定的1024，不管输入规模n怎么变大，它的值都不会改变，属于**O(1)**级别的常数增长，是所有函数里最慢的。

线性阶：2^logn、3n+100logn、4n #

这三个函数都属于线性增长级别：

• 2^logn：算法分析里默认log以2为底，根据对数和指数的互逆关系，2^log₂n = n，所以它的渐近复杂度是O(n)。
• 3n+100logn：当n足够大时，线性项3n的增长速度会完全盖过对数项100logn，所以我们可以忽略低阶的对数项，复杂度为O(n)。
• 4n：标准的线性函数，直接就是O(n)。
  这三个之间只有常数因子的差异，不影响渐近增长率的排序，所以归为同一组。

线性对数阶：nlogn、4nlogn+2n #

• nlogn：这是算法里非常常见的复杂度，比如归并排序、快速排序的平均时间复杂度都是这个级别。
• 4nlogn+2n：当n增大时，4nlogn的增长速度远快于线性项2n，所以忽略低阶项后，复杂度也是O(nlogn)，和nlogn属于同一增长级别。

平方阶：n^2 + 10n #

平方项n²的增长速度比线性项10n快得多，当n足够大时，线性项可以忽略不计，所以复杂度是O(n²)，比如冒泡排序的最坏情况就是这个复杂度。

立方阶：n^3 #

立方阶的增长速度比平方阶更快，复杂度为O(n³)，比如一些朴素的三重循环算法（比如原生矩阵乘法）就属于这个级别。

指数阶：2^n #

这是所有函数里增长最快的，随着n的增大，2^n会呈现爆炸式增长，比如暴力枚举所有子集的算法时间复杂度就是O(2ⁿ)，这类算法通常只适用于极小的输入规模。

内容的提问来源于stack exchange，提问作者pc.97