Vik*_*hat 13
合并有三种方法: -
假设你正在合并m lists与n elements each
算法1: -
合并列表一次两个.使用合并排序(如合并例程)进行合并,因为列表已排序.没有任何库,这很容易实现.但是O(m^2*n)如果m不大,则需要足够小的时间.
算法2: -
这是对1的改进,其中我们总是合并列表,这是剩余列表中最小的两个.使用a priority queue执行此操作并选择最小的两个列表并合并它们并将新列表添加到队列.这样做直到只留下一个列表,这将是你的答案.该技术用于huffman coding并生产optimal merge pattern.这需要O(m*n*logm).此外,对于类似大小的列表,可以制作,parallel因为我们可以选择一对列表并且并行合并.假设你有m processors算法可以理想地运行O(n*logm)而不是O(m*n*logm)
算法3: -
这是最有效的算法,您可以在其中维护priority queue所有列表的第一个元素并提取min以获取新元素,同时维护列表min元素所属的索引,以便您可以添加该列表中的下一个元素.这取决于O(s*logm)s是所有列表中的总元素.
以下方法适用于任何容器,如数组,向量,列表等.我假设我们正在使用列表.
我们假设我们已经m对要合并的列表进行了排序.
Let n表示所有列表中的元素总数.
结果列表中的第一个元素必须是列表中所有头部集合中的最小元素.
这个想法很简单.只需选择最小的头并将其从原始列表移动到结果.您希望在至少有一个非空列表时重复该例程.这里至关重要的是快速选择最小的头部.
甲线性扫描通过磁头被O(m)导致O(m * n)如果其是精细总时间m是一个很小的常数.
然后我们可以通过使用优先级队列(例如堆)来做得更好.这里的不变量是堆中的最小元素始终是当前头中的最小元素.
查找最小元素是堆O(1),删除最小值是堆中O(log m)是否有m元素,并且还将元素插入堆中O(log m).
总之,对于每个n元素,我们将其插入到堆中一次并从那里删除一次.如果不是一个小的常量O(n log m),堆的总复杂性明显更快.O(n * m)m
哪种方法更快取决于我们要合并的列表数量.如果m小则选择线性扫描,在另一种情况下用优先级队列实现它.有时很难判断它m是否很小,在这种情况下,一些实验会有所帮助.