Почему сортировка не занимает O (n log (n)) во времени

Question

В следующем фрагменте расход времени равен std::sort. Это должно занять O (nlog (n)) время. std::chrono используется исключительно для измерения std::sort.

Я скомпилировал следующий код с помощью компилятора Intel 18.0.3 с уровнем оптимизации -O3. Я использую Redhat6.

#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.

Кажется, это очень близко к линейному поведению.

Почему std::sort требует O(n), а не O(nlog(n))?

Answer 1

График, который вы представляете, подходит для y = x log (x).По сравнению с x, log(x) имеет небольшой эффект.Я полагаю, что ваши результаты прошли бы через квадрат хи для x log (x) с хорошим значением.

Здесь нет никаких сюрпризов.

Это пробный камень для вашей оценки того, что O (n log n) ненамного хуже, чем O (n).