0

假设您有这种快速排序实现，它可能与标准实现有点不同：

qsort(list):
if list is of length 1 or lower - 
     return list
else - 
     choose a random pivot 
     smaller - get all elements that are smaller than the pivot
     equal - get all elements that are equal to the pivot, including the pivot itself
     greater - get all elements that are greater than the pivot
     return qsort(smaller) + equal + qsort(greater)

当函数接收到所有元素都相同的列表时，该函数的最佳情况不是吗，在这种情况下，最佳情况时间复杂度将是O(n)，这比标准的最佳情况时间复杂度要好快速排序的版本，哪个是O(n log n)？

这样做的原因是该函数只创建一次这些分区，因为更小和更大的列表都是空的（因为所有元素都是相同的），这将结束递归，qsort(smaller)并且qsort(greater)只会返回空列表。

那是对的吗？

4

1 回答 1

1

是的，在您描述的情况下，时间复杂度将为O(n).

但是，该空间也将O(n)作为equal需要创建的新列表。更糟糕的是 qsort 就地排序，因此具有O(1)（恒定的）空间要求。

的 qsort 时间复杂度O(n lg(n))是假设统计随机数据计算的平均情况。您的适应将有助于在所有值都相等的边缘情况下提高性能，这是非常不可能的（尽管您可能对数据有先验知识，这使得它更有可能）。

如果您正在考虑使用此算法而不是标准 qsort，我建议您不要使用它。由于使用额外列表会增加添加元素和连接的开销（此开销取决于列表的实现）。qsort 中不存在此开销，因为它排序到位。

于 2013-07-11T12:40:03.283 回答