为何std::sort的时间复杂度看似接近O(n)而非O(n log n)？

首先，咱们先看一下你用来测试的代码：

#include <vector>
#include <random>
#include <limits>
#include <iostream>
#include <chrono>
#include <algorithm>
int main() {
    std::random_device dev;
    std::mt19937 rng(dev());
    std::uniform_int_distribution<std::mt19937::result_type> dist(std::numeric_limits<int>::min(), std::numeric_limits<int>::max());
    int ret = 0;
    const unsigned int max = std::numeric_limits<unsigned int>::max();
    for (auto j = 1u; j < max; j *= 10) {
        std::vector<int> vec;
        vec.reserve(j);
        for (int i = 0; i < j; ++i) {
            vec.push_back(dist(rng));
        }
        auto t_start = std::chrono::system_clock::now();
        std::sort(vec.begin(), vec.end());
        const auto t_end = std::chrono::system_clock::now();
        const auto duration = std::chrono::duration_cast<std::chrono::duration<double>>(t_end - t_start).count();
        std::cout << "Time measurement: j= " << j << " took " << duration << " seconds.\n";
        ret + vec[0];
    }
    return ret;
}

以及对应的输出：

Time measurement: j= 1 took 1.236e-06 seconds.
Time measurement: j= 10 took 5.583e-06 seconds.
Time measurement: j= 100 took 1.0145e-05 seconds.
Time measurement: j= 1000 took 0.000110649 seconds.
Time measurement: j= 10000 took 0.00142651 seconds.
Time measurement: j= 100000 took 0.00834339 seconds.
Time measurement: j= 1000000 took 0.098939 seconds.
Time measurement: j= 10000000 took 0.938253 seconds.
Time measurement: j= 100000000 took 10.2398 seconds.
Time measurement: j= 1000000000 took 114.214 seconds.
Time measurement: j= 1410065408 took 163.824 seconds.

看起来时间增长确实和j的增长近乎线性，但这其实是一种视觉错觉，核心原因有几个：

1. log₂(n)的增长速度慢到超乎想象 #

复杂度里的log n项增长极其平缓，当n从1增加到10亿时，log₂(n)只从0增长到约30——也就是说，n log n的增长里，n的主导性极强，log n的变化很难从直观的时间数值里一眼看出来。

咱们可以计算每个测试点的时间 / (n * log₂(n))，看看这个比值是不是大致稳定：

• 当j=1e6时：0.098939 / (1e6 * 20) ≈ 4.94e-9
• 当j=1e7时：0.938253 / (1e7 * 23.25) ≈ 4.03e-9
• 当j=1e8时：10.2398 / (1e8 * 26.57) ≈ 3.85e-9
• 当j=1e9时：114.214 / (1e9 * 30) ≈ 3.8e-9

可以看到这个比值基本稳定，说明时间确实和n log n成正比，只是因为log n的增长太缓慢，让你误以为是线性增长。

2. 测试步长放大了线性的错觉 #

你用的是j *= 10的循环步长，每次n翻10倍，而log₂(n)只增加约3.32（因为log₂(10)≈3.32）。当n很大时，n log n的增长比例接近10，但实际会略大于10——比如从1e8到1e9，n log n的比例是10*(30/26.57)≈11.29，而时间比例是114.214/10.2398≈11.15，几乎完全吻合，这就实锤了复杂度是O(n log n)。

3. Intel编译器的极致优化放大了常数因子的影响 #

你用的是Intel ICC 18.0.3 + -O3优化，这个编译器对std::sort做了非常深度的优化：它会根据数据规模自动切换算法（小数据用插入排序，大数据用快速排序/归并排序的混合实现），还会利用SIMD指令加速比较和交换操作，让n log n里的常数因子变得非常小。这进一步让log n的影响更难被直观察觉，但本质上复杂度并没有改变。

总结 #

你的测试结果其实完全符合std::sort的O(n log n)时间复杂度，只是因为log n的增长速度太慢，加上测试步长的选择，才给了你“接近线性”的错觉。通过计算时间和n log n的比值，就能清晰看到两者的正比关系。

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