为什么排序不及时获取O(n log(n))

本文介绍了为什么排序不及时获取O(n log(n))的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

在以下代码段中，std::sort的时间消耗.这应该需要 O(nlog(n))时间. std::chrono仅用于测量std::sort.

In the following snippet the time consumption of std::sort. This should take O(nlog(n)) time. std::chrono is used solely measuring std::sort.

我使用优化级别为-O3的Intel编译器18.0.3编译了以下代码.我使用Redhat6.

I compiled the following code with the Intel compiler 18.0.3 with optimization level -O3. I use 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.

这似乎非常接近线性行为.

This seems to be very close to linear behaviour.

为什么std::sort需要O(n)而不是O(nlog(n))?

推荐答案

您呈现的图形非常适合y = x log (x).与x相比，log(x)的影响很小.我认为您的结果将通过具有很好意义的x log (x)的卡方.

The graph you present is a good fit for y = x log (x). Compared to x, log(x) has a small effect. I conject your results would pass a chi square for x log (x) with good significance.

这里没有惊喜.

这是您欣赏O(n log n)并不比O(n)差很多的试金石.

This is a touchstone for your appreciation that O(n log n) isn't much worse than O(n).