algorithm - 这些输入的合并排序的运行时间是多少

Question

我正在尝试确定 Big O 合并排序的运行时间:

(A) 排序输入

(B) 逆序输入

(C) 随机输入

我的答案是，对于所有三种情况都需要 O(n lgn)，因为无论输入的默认顺序如何，合并排序总是将输入划分为 1 个元素的最小单元。然后它将每个元素与相邻列表中的每个元素进行比较，以对两个相邻列表进行排序和合并。它将继续这样做，直到最终所有元素都被排序并合并。

也就是说，我们真正需要找到的是归并排序的 Big O 复杂度，因为最坏、平均和最好的情况都需要相同的时间。

我的问题是，有人可以告诉我我的答案是否正确，如果是，请解释为什么归并排序的 Big O 复杂度最终是 O(n lgn)？

Answer 1

这个问题的答案取决于您的归并排序的实现。 当天真的实现时，合并排序确实使用 O(n * log n) 时间，因为它总是将输入划分为最小单元。然而，有一个名为自然合并排序的特定实现，如果数字已经在输入数组中排序，则该实现将保持数字的正确顺序，方法是首先查看给定的输入并决定需要对哪些部分进行排序。有序，即划分然后再合并。

自然归并排序对于有序输入仅花费 O(n) 时间，并且通常对于随机输入比对于逆序输入更快。在后两种情况下，运行时间将为 O(n * log n)。

为了回答你的最后一个问题，我将看看“正常”合并排序；这样解释就更容易了。

请注意，合并排序可以可视化为一棵二叉树，其中根部有整个输入，下一层是输入一次划分后得到的两半，第三层有四个四分之一，依此类推。 ..在最后一层，我们终于有了单独的数字。

然后注意整棵树的深度是 O(log n) (这也可以用数学证明)。在每一层上，我们必须对总共 n 个数字进行一些比较和交换 - 这是因为当我们沿着树向下走时，一层上的数字总数不会减少。图中，我们需要对每层8个数字进行比较和交换。按照合并排序的工作方式，我们实际上必须在每层精确 8 次比较和最多 8 次交换。如果我们的输入长度为 n 而不是 8，则每层需要 n 次比较和最多 n 次交换(这是 O(n))。我们有 O(log n) 层，因此整个运行时间将为 O(n * log n)。