在一个以K-路合并合并和项目的数量之间的关系是什么 [英] What is the relation between merges and number of items in a in k-way merge

问题描述

现在的问题是：在K-路合并，有多少合并操作，我们将执行。 例如：2路合并：2节点1的合并; 3个节点2合并; 4个节点3合并。所以，我们得到M（N）= N-1。

The question is: In a k-way merge, how many merge operation will we perform. For example: 2-way merge:2 nodes 1 merge; 3 nodes 2 merge; 4 nodes 3 merge. So we get M(n)=n-1.

什么的M（N）当k是任意的？

What the the M(n) when k is arbitrary?

推荐答案

确定，要回答原来的规定的问题：

OK, to answer the original question as stated:

要合并的 K 的使用序列的2路合并的总是的要求完全块的 K 的 - 1的合并，因为无论什么对的块选择合并在任何时间点，将它们合并1降低块的总数量。

To merge k blocks using a sequence of 2-way merges always requires exactly k - 1 merges, since regardless of what pair of blocks you choose to merge at any point in time, merging them reduces the total number of blocks by 1.

正如我在原来的答复，你选择对块的合并说的确实的影响，总的时间复杂度 - 这是更好地合并同类大小的块 - 但它并不影响中的号的2路合并操作。

As I said in my original answer, which pairs of blocks you choose to merge does impact the overall time complexity -- it's better to merge similar-sized blocks -- but it doesn't affect the number of 2-way merge operations.

这篇关于在一个以K-路合并合并和项目的数量之间的关系是什么的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！