Dav*_*aio 65
该合并排序使用分而治之的方法来解决排序问题.首先,它使用递归将输入分成两半.分割后,它对半部分进行排序并将它们合并为一个有序输出.见图
这意味着最好先对问题的一半进行排序,然后执行简单的合并子例程.因此,了解merge子例程的复杂性以及在递归中调用它的次数非常重要.
合并排序的伪代码非常简单.
# C = output [length = N]
# A 1st sorted half [N/2]
# B 2nd sorted half [N/2]
i = j = 1
for k = 1 to n
if A[i] < B[j]
C[k] = A[i]
i++
else
C[k] = B[j]
j++
这是很容易看到,在每个循环中,您将有4个操作:ķ++,我++或J ++的if语句和归属C = A | B.因此,您将具有小于或等于4N + 2个运算,从而产生O(N)复杂度.为了证明,4N + 2将被视为6N,因为对于N = 1(4N + 2 <= 6N)是正确的.
因此,假设您有一个包含N个元素的输入,并假设N是2的幂.在每个级别,您有两倍的子问题,其输入具有前一个输入的半个元素.这意味着在级别j = 0,1,2,...,lgN处将存在具有长度N/2 ^ j的输入的2 ^ j个子问题.每个级别j的操作次数将小于或等于
2 ^ j*6(N/2 ^ j)= 6N
观察到它总是具有少于或等于6N操作的水平并不重要.
由于lgN + 1级别,复杂性将是
O(6N*(lgN + 1))= O(6N*lgN + 6N)= O(n lgN)
参考文献:
sup*_*cat 33
在"传统"合并排序中,每次传递数据都会使排序的子部分的大小加倍.在第一次传递之后,文件将被分类为长度为2的部分.第二次传球后,长度为四.然后八,十六等达到文件的大小.
有必要将排序部分的大小加倍,直到有一个部分包含整个文件.将截面大小的lg(N)倍增达到文件大小,并且每次传递数据将花费与记录数量成比例的时间.
- 这是一个很好的答案,但在我得到它之前我必须阅读它几次.一个例子可能会有所帮助......例如,假设您有一个包含8个数字的列表.你将它们分成长度为1的子列表.它需要3次加倍或lg(8)才能获得8个成员的列表.在Word案例场景中,您必须检查每个子列表的每个成员一次,这意味着对于所有三次加倍,您必须检查所有8个值. (14认同)
Pan*_*and 20
这是因为无论是最坏情况还是普通情况,合并排序只是在每个阶段将数组分成两半,从而得到lg(n)分量,而另一个N分量来自在每个阶段进行的比较.因此,它的组合几乎变为O(nlg n).无论是平均情况还是最坏情况,lg(n)因子总是存在.休息N因子取决于在两种情况下进行的比较所得到的比较.现在最糟糕的情况是在每个阶段对N个输入进行N次比较.所以它变成了O(nlg n).
blu*_*kin 18
将数组拆分到具有单个元素的阶段后,即将它们称为子列表,
在每个阶段,我们将每个子列表的元素与其相邻的子列表进行比较.例如,[重用@Davi的图像]
- 在阶段-1,将每个元素与其相邻元素进行比较,因此进行n/2比较.
- 在阶段-2,将子列表的每个元素与其相邻子列表进行比较,因为每个子列表都被排序,这意味着两个子列表之间的最大比较次数是<=子列表的长度,即2(在阶段-2)和由于子列表的长度增加了一倍,因此在阶段3的阶段3和阶段4进行了4次比较.这意味着每个阶段的最大比较数=(子列表的长度*(子列表的数量/ 2))==> n/2
- 正如您所观察到的阶段
log(n) base 2总数那样,总复杂度将是== (每个阶段的最大比较数*阶段数)== O((n/2)*log(n))== > O(nlog(n))
许多其他答案都很棒，但我没有看到任何与“合并排序树”示例相关的高度和深度的提及。这是另一种解决问题的方法，重点放在树上。这是另一张有助于解释的图像：
简单回顾一下：正如其他答案所指出的，我们知道合并序列的两个排序切片的工作在线性时间内运行（我们从主排序函数调用的合并辅助函数）。
现在看这棵树，我们可以将根的每个后代（根除外）视为对排序函数的递归调用，让我们尝试评估我们在每个节点上花费的时间......序列和合并（两者一起）需要线性时间，任何节点的运行时间相对于该节点的序列长度是线性的。
这就是树深度的用武之地。如果 n 是原始序列的总大小，则任何节点上的序列大小都是 n/2 i，其中 i 是深度。这如上图所示。将其与每个切片的线性工作量放在一起，我们对树中的每个节点都有O(n/2 i )的运行时间。现在我们只需要对 n 个节点进行总结。这样做的一种方法是识别在树中每个深度级别有 2 i 个节点。所以对于任何级别，我们都有 O(2 i * n/2 i )，这是 O(n)，因为我们可以抵消 2 i s！如果每个深度都是 O(n)，我们只需将其乘以高度这个二叉树的，它是logn。答案：O(nlogn)
- 很好的解释！谢谢。 (2认同)
递归树将具有深度log(N)，并且在该树的每个级别上，您将进行组合N工作来合并一对或多对排序数组。
- \n
- 您递归地将起始数组分成两半，直到最终得到
N每个包含单个元素的数组。因为只有一个元素，所以这些数组在技术上是按 \xe2\x80\x94 排序的，这一点很重要。 \n - 现在，您可以通过使用排序算法重新组合每个已排序的数组来展开递归
O(N)（如下所示）。 \n
合并排序数组
\n要合并两个已排序的数组A[1,5]，B[3,4]只需从头开始迭代这两个数组，选择两个数组之间的最低元素并递增该数组的指针。当两个指针都到达各自数组的末尾时，您就完成了。
表示^迭代每个数组时各自的索引。
[1,5] [3,4] --> []\n ^ ^\n\n[1,5] [3,4] --> [1]\n ^ ^\n\n[1,5] [3,4] --> [1,3]\n ^ ^\n\n[1,5] [3,4] --> [1,3,4]\n ^ x\n\n[1,5] [3,4] --> [1,3,4,5]\n x x\n\nRuntime = O(A + B)\n合并排序图
\n您的递归调用堆栈将如下所示。工作从底部叶节点开始并向上冒泡。
\nbeginning with [1,5,3,4], N = 4, depth k = log(4) = 2\n\n [1,5] [3,4] depth = k-1 (2^1 nodes) * (N/2^1 values to merge per node) == N\n[1] [5] [3] [4] depth = k (2^2 nodes) * (N/2^2 values to merge per node) == N\n因此，您可以在树的N每个级别上进行工作，其中kk = log(N)
N * k = N * log(N)