算法:得到O(n lg n/ lg k)算法而不是O(n lg n/k)算法

Question

假设您有一台特殊的高性能计算机。在这台计算机中，有一个专门的k优化寄存器库，其中k> 2。每个寄存器都可以用来存储一个键值对，因此这组寄存器可以存储到k个键值对。此登记册库可在O(1)时间内支持下列操作：

• 将键值对(x，y)插入此寄存器库；以及
• 返回一个键值对(x，y)，它是最小的键x，从寄存器库中返回.此返回对也将从此寄存器库中删除。

设计了一种利用这组寄存器在O(n lg n/ lg k)时间内对n个数字进行排序的算法。

这就是问题所在。我是用分而治之的方法做的。我认为这与合并类似。然而，我只能得到一个有O(n lg n/k)的算法。在大多数情况下，O(n lg n/k)比O(n lg n/ k)慢，所以我想知道如何思考这个问题。谢谢。

Answer 1

通常，将K排序列表与总共N个元素合并需要O(N )时间，使用这样的算法将输入列表保持在优先级队列中，然后重复从所有头项中选择最小的元素：https://www.geeksforgeeks.org/merge-k-sorted-arrays/

你的魔法注册库允许你在O(N)时间内进行K路合并.您可以通过使用该功能实现合并排序来获得所需的结果，但不是在每个级别执行双向合并，而是在每个级别进行K-way合并：

• 在O(N)总时间内对所有长度-K子列表进行排序
• 将每组K列表合并为O(N)总时间内的长度K^2列表
• 同样可以创建长度为K^3等的列表。

排序将花费O(N)每级* log_k(N)级，总共O(N log_k(N)) = O(N log(N)/log(K))时间