时间复杂度含义解析及归并排序n log(n)理论与实际时间对比疑问

我接到的任务是通过不同数据量n对应的耗时，在图表中展示归并排序算法的理论耗时（n log(n)）与实际程序耗时。我在程序中通过记录调用mergeSort函数前后的时间差来获取实际耗时，单位为微秒，现在想搞清楚n log(n)的具体含义。

测试数据 #

计时实现代码 #

auto start = std::chrono::high_resolution_clock::now();
mergeSort(arr, 0, n - 1);
auto elapsed = std::chrono::high_resolution_clock::now() - start;
long long microseconds = std::chrono::duration_cast<std::chrono::microseconds>(elapsed).count();
cout << microseconds << " ";

耗时对比图表 #

关于n log(n)的含义 #

归并排序是典型的分治算法，它的时间复杂度用大O表示法记作O(n log n)，这里的n log(n)是对算法执行时的操作量级的描述：

• n代表要排序的数据总量，算法在合并阶段需要遍历所有元素，这部分的操作次数和n成正比；
• log n是分治过程的层数：归并排序会不断把数据分成两半，直到每个子数组只有1个元素，这个拆分的次数就是以2为底n的对数（通常写log n时默认底数为2）；
• 每一层的合并操作总次数都是O(n)，总共log n层，所以整体的操作量级就是n × log n。

你计算的n log(n)数值是理论上的操作次数参考值，但实际耗时会和这个数值成线性比例——因为实际运行时，每个操作的执行时间受CPU性能、内存访问、编译器优化等因素影响，所以实际耗时的数值会比理论计算的操作次数小很多。从你的图表也能看出两者的趋势完全一致，这就验证了归并排序的时间复杂度确实是O(n log n)。

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