algorithm - 合并排序迭代次数

Question

可能重复：
为什么合并排序中的合并操作是 O(n)？

为什么每次迭代都需要 O(n) 关于合并排序有人可以为我详细解释一下吗？为什么 C_merge(n)= O(n)？这是否意味着合并两个排序数组的时间。

Answer 1

这个想法是我们有两个排序数组，而不是两个数组，其中一个的最小元素大于另一个最大的元素。我的意思是，它不是[1, 3, 9, 12]and [13, 17, 19]。但它更像[3, 12, 13, 17]和[1, 9, 19]。

你看，在以后的情况下你不能附加它们。那么，如何结合？您遵循以下算法：

1. 可以说第一个有m元素，第二个有n。您制作了一个 size 的辅助数组m+n。这将存储最终组合和排序的数组。
2. 分配两个光标 --i和j，指向数组的头部。
3. i比较和处的元素j；选择较小的那个。复制值辅助数组，并将光标移动到更小的光标前面。
4. 重复#3，直到其中一个阵列耗尽；然后将剩余的元素从未用尽的数组复制到辅助数组。

所以，在我们的例子中，你比较(3, [1]); ([3], 9); (12, [9]); ([12], 19); ([13], 19); ([17], 19); (--, [19]) . 你看？怎么可能比较？(m+n). 假设每次操作O(1)。长度数组的合并过程(m+n)是O(m+n).

在最好的情况下，您将排序数组作为输入。例如，要合并的两个子数组只需要加入。但是我们将应用上面提到的通用算法。在这种情况下，您将不得不比较和复制min(m,n)元素；然后将max(m,n)元素复制到辅助数组。在任何情况下，您都将进行全面(m+n)操作。