algorithm - 归并排序的时间复杂度

Question

为什么自上而下合并排序的最佳情况的时间复杂度在 O(nlogn) 中？我认为自上而下合并排序的最佳情况是 1，只需要比较 1 次。在最坏情况，最佳情况和平均情况下，自下而上合并排序的时间复杂度如何。

还有一个问题是为什么每次迭代都需要 O(n)？有人可以帮忙吗？

Answer 1

为什么自上而下合并排序的最佳情况的时间复杂度在 O(nlogn) 中？

因为在每次迭代中，您将数组拆分为两个子列表，并递归调用算法。在最好的情况下，您将其完全拆分为一半，从而将（每个递归调用的）问题减少到原始问题的一半。您需要 log_2(n) 次迭代，并且每次迭代都精确O(n)（每次迭代都在所有子列表上，总大小仍然是n），所以在 total O(nlogn)。

但是，通过简单的预处理来检查列表是否已经排序 - 它可以简化为O(n).

由于检查列表是否已排序本身O(n)- 它不能在O(1). 请注意，“最佳情况”是 general 的“最佳情况” n，而不是特定大小。

在最坏情况，最佳情况和平均情况下，自下而上合并排序的时间复杂度如何。

同样的方法可以为您提供 O(n) 自下而上的最佳情况（简单的预处理）。自下而上合并排序的最坏情况和最好情况是O(nlogn)- 因为在这种方法中，列表总是被分成 2 个等长（直到差异 1）列表。