这些输入的合并排序的 运行 时间是多少
What is the running time of merge sort for these inputs
我正在尝试确定 运行 合并排序的 Big O 时间：
(A) 排序输入
(B) 逆序输入
(C) 随机输入
我的回答是所有三种情况都需要 O(n lgn)，因为无论输入的默认顺序如何，归并排序总是将输入划分为 1 个元素的最小单元。然后它将每个元素与相邻列表中的每个元素进行比较，以对两个相邻列表进行排序和合并。它将继续这样做，直到最后所有元素都被排序和合并。
也就是说，我们真正需要找到的只是一般合并排序的 Big O 复杂度，因为最坏、平均和最好的情况都需要相同的时间。
我的问题是，有人能告诉我我的答案是否正确吗？如果正确，请解释为什么归并排序的 Big O 复杂度最终会变成 O(n lgn)？
这个问题的答案取决于您对合并排序的实现。
当天真地实现时，合并排序确实使用 O(n * log n) 时间，因为它总是将输入划分为最小单位。但是，有一个名为 Natural Merge Sort 的特定实现，如果数字已经在输入数组中排序，它会通过首先查看给定输入并决定哪些部分来保持数字的正确顺序需要排序，即分而后合并。
对于有序输入，自然合并排序只需要 O(n) 时间，并且对于随机输入通常比对于逆序输入更快。在后两种情况下，运行时间将为 O(n * log n).
为了回答您的最后一个问题，我将查看 "normal" 合并排序；这样解释起来更容易。
请注意，Mergesort 可以可视化为一棵二叉树，在根中我们有整个输入，在下一层，你将输入分成两半，在第三层，我们有四个四分之一等等on...在最后一层我们终于有了个人数字。
然后注意整棵树的深度是O(log n)（这也可以用数学证明）。在每一层上，我们必须对总共 n 个数字进行一些比较和交换——这是因为当我们沿着树向下走时，一层上的数字总数不会减少。图中，我们需要对每一层的8个数进行比较和交换。按照 Mergesort 的工作方式，我们实际上必须进行 exactly 8 次比较，并且每层 up to 8 次交换。如果我们有一个长度为 n 而不是 8 的输入，我们将需要 n 次比较和每层最多 n 次交换（这是 O(n)）。我们有 O(log n) 层，所以整个运行时间为 O(n * log n)。
我正在尝试确定 运行 合并排序的 Big O 时间：
(A) 排序输入
(B) 逆序输入
(C) 随机输入
我的回答是所有三种情况都需要 O(n lgn)，因为无论输入的默认顺序如何，归并排序总是将输入划分为 1 个元素的最小单元。然后它将每个元素与相邻列表中的每个元素进行比较，以对两个相邻列表进行排序和合并。它将继续这样做，直到最后所有元素都被排序和合并。
也就是说，我们真正需要找到的只是一般合并排序的 Big O 复杂度，因为最坏、平均和最好的情况都需要相同的时间。
我的问题是，有人能告诉我我的答案是否正确吗？如果正确，请解释为什么归并排序的 Big O 复杂度最终会变成 O(n lgn)？
这个问题的答案取决于您对合并排序的实现。 当天真地实现时，合并排序确实使用 O(n * log n) 时间，因为它总是将输入划分为最小单位。但是，有一个名为 Natural Merge Sort 的特定实现，如果数字已经在输入数组中排序，它会通过首先查看给定输入并决定哪些部分来保持数字的正确顺序需要排序，即分而后合并。
对于有序输入，自然合并排序只需要 O(n) 时间，并且对于随机输入通常比对于逆序输入更快。在后两种情况下，运行时间将为 O(n * log n).
为了回答您的最后一个问题，我将查看 "normal" 合并排序；这样解释起来更容易。
请注意，Mergesort 可以可视化为一棵二叉树，在根中我们有整个输入，在下一层，你将输入分成两半，在第三层，我们有四个四分之一等等on...在最后一层我们终于有了个人数字。
然后注意整棵树的深度是O(log n)（这也可以用数学证明）。在每一层上，我们必须对总共 n 个数字进行一些比较和交换——这是因为当我们沿着树向下走时，一层上的数字总数不会减少。图中，我们需要对每一层的8个数进行比较和交换。按照 Mergesort 的工作方式，我们实际上必须进行 exactly 8 次比较，并且每层 up to 8 次交换。如果我们有一个长度为 n 而不是 8 的输入，我们将需要 n 次比较和每层最多 n 次交换（这是 O(n)）。我们有 O(log n) 层，所以整个运行时间为 O(n * log n)。