k路归并是一种算法,它将k个大小为n的排序数组作为输入,并输出一个包含所有元素的单个已排序数组。
这是通过使用与合并排序算法中心相同的“合并”例程来将第1个数组合并到第2个数组,然后将第3个数组合并到此合并数组中,以此类推,直到所有k个数组都合并为止。
我曾认为该算法的时间复杂度为O(kn),因为该算法遍历每个长度为n的k个数组各一次。但为什么时间复杂度是O(nk^2)呢?
k路归并是一种算法,它将k个大小为n的排序数组作为输入,并输出一个包含所有元素的单个已排序数组。
这是通过使用与合并排序算法中心相同的“合并”例程来将第1个数组合并到第2个数组,然后将第3个数组合并到此合并数组中,以此类推,直到所有k个数组都合并为止。
我曾认为该算法的时间复杂度为O(kn),因为该算法遍历每个长度为n的k个数组各一次。但为什么时间复杂度是O(nk^2)呢?
因为它没有遍历 k 个数组,每个数组只被遍历了 k-1 次。第一个数组被遍历了 k-1 次,第一次是合并 (array-1,array-2),第二次是合并 (merge(array-1, array-2), array-3) ... 以此类推。
结果是 k-1 次合并,平均大小为 n*(k+1)/2,复杂度为 O(n*(k^2-1)/2),即 O(nk^2)。
你犯的错误是忘记了这些合并是串行完成而不是并行完成,因此这些数组的大小不都是 n。
事实上,在最坏的情况下,第一个数组将进行n次比较,第二个数组将进行2n次比较,第三个数组将进行3n次比较,以此类推,直到第(k - 1)n个数组。
因此,现在复杂度变得简单了。
n + 2n + 3n + 4n + ... + (k - 1)n
= n(1 + 2 + 3 + 4 + ... + (k - 1))
= n((k - 1)*k) / 2
= n(k^2 - k) / 2
= O(nk ^ 2)
:-)
这样怎么样:
步骤1: 合并数组(1和2),数组(3和4),以此类推。(k/2个长度为2n的数组合并,总工作量为kn)。
步骤2: 合并数组(1,2和3,4),数组(5,6和7,8),以此类推。(k/4个长度为4n的数组合并,总工作量为kn)。
步骤3: 重复…
会有log(k)个这样的“步骤”,每个步骤的工作量为kn。因此总工作量为O(k.n.log(k))。
即使我们只是对数组的所有元素进行排序,我们仍然可以在O(k.n.log(k.n))的时间内合并所有元素。
您无需每次逐个比较项目。您只需在已排序的集合中维护最近的K个项目。您删除最小的并用其下一个元素替换它。这应该是n.log(k)。
相关文章。免责声明:我参与了撰写
1) 你有k个已排序的数组,每个数组的大小均为n。因此元素的总数为k * n。
2) 取出所有k个数组的第一个元素,并创建一个序列。然后找到这个序列中的最小值。将此最小值存储在输出数组中。查找k个元素的最小值所需的比较次数为k-1次。
3) 因此,总比较次数为:
=(每个元素的比较次数)* 元素的数量
=(k-1)* k * n
= k ^ 2 * n //近似值
一种常见的实现方式是为每个排序数组 {i_1, i_2, i__k} 保留一个索引数组。在每次迭代中,算法从这 k 个数组中找到下一个最小元素,并将其存储在输出数组中。由于您将对 k 个数组进行 kn 次迭代和扫描,总复杂度为 O(k^2 * n)。
以下是伪代码:
Input: A[j] j = 1..k : k sorted arrays each of length n
Output: B : Sorted array of length kn
// Initialize array of indexes
I[j] = 0 for j = 1..k
q = 0
while (q < kn):
p = argmin({A[j][I[j]]}) j = 1..k // Get the array for which the next unprocessed element is minimal (ignores arrays for which I[j] > n)
B[q] = A[p][I[p]]
I[p] = I[p] + 1
q = q + 1
您有k个数组,每个数组有n个元素。这意味着总共有k*n个元素。
将其视为一个k*n的矩阵。要将第一个元素添加到合并/最终数组中,您需要比较k个数组的头部。这意味着对于最终数组中的一个元素,您需要进行k次比较。
因此,根据1和2,对于Kn个元素,所需的总时间为O(kk*n)。
对于那些想要了解细节或需要一些帮助的人,我将扩展Recurse的答案和后续评论
k-1
次合并,因为最后一个数组不会与任何东西合并Sn=n(a1 + an)2
通过k
个具有n
个元素的数组的前4次合并进行步进
+-------+-------------------+-------------+
| Merge | Size of new array | Note |
+-------+-------------------+-------------+
| 1 | n+n = 2n | first merge |
| 2 | 2n+n = 3n | |
| 3 | 3n+n = 4n | |
| 4 | 4n+n = 5n | |
| k-1 | (k-1)n+n = kn | last merge |
+-------+-------------------+-------------+
k-1
)。使用求和前n
项的公式Sn=n(a1 + an)2
,我们只需要第一个和最后一个项:
2n
(第一项)kn
(最后一项)n=k-1
(我们拥有的项数)。代入数字,我们得到所有项的总和公式
Sn = ( (k-1)(2n+kn) )/2
然而,为了找到平均大小,我们必须除以项数(k-1
)。这会消去分子中的k-1
,留下平均大小为
(2n + kn)/2
现在我们有了平均大小,我们可以将其乘以合并的数量,即k-1
。为了使乘法更容易,忽略/2
,只需将分子相乘即可: (k-1)(2n+kn)
= (k^2)n + kn - 2n
此时您可以重新引入/2
,但是没有必要,因为显然主导项是(k^2)*n