sorting - 归并排序的运行时间 :: 所有元素都相同

Question

假设我们有一个大小为 n 的数组，其中所有元素都相同。O(n) 会是多少？会是线性的吗？

Answer 1

这取决于算法是如何实现的。

使用合并排序的标准“普通”实现，对数组进行排序所需的时间将始终为 Θ(n log n)，因为每个步骤所需的合并都需要线性时间。

然而，通过适当的优化，它可以在 O(n) 时间内运行。在许多合并排序实现中，输入数组不断修改，以便对越来越大的范围进行排序，并且当发生合并步骤时，该算法使用外部缓冲区来合并两个相邻的排序范围。在这种情况下，您可以做一个漂亮的优化：在进行合并之前，检查第一个范围的最后一个元素是否小于或等于第二个范围的第一个元素。如果是这样，则两个加在一起的范围已经排序，因此不需要进行合并。

假设您执行此优化并尝试对所有元素都已排序的数组进行排序。怎么了？好吧，对 mergesort 的每次调用都会触发另外两个递归调用。在这些返回之后，它可以检查排序范围的端点，并会注意到它们已经按排序顺序，所以没有更多的工作要做。总体而言，每次调用的时间复杂度为 O(1)，因此对于算法的时间复杂度，我们有这个递归关系：

T(n) = 2T(n/2) + O(1)

这解决了 O(n)，因此只完成了线性工作。