假设您有一台特殊的高性能计算机。在这台电脑里， 有一个专门的 k 个优化寄存器组，其中 k > 2。这些寄存器中的每一个都可以用来存储一个键值对，因此这组寄存器最多可以存储 k 个键值对。该寄存器组可以在 O(1) 时间内支持以下操作:
- 将键值对 (x, y) 插入到这组寄存器中；和
- 返回一个键值对 (x, y)，它是寄存器组中最小的键 x。这个返回的对也从这个寄存器库中删除。
设计一种算法，可以利用这组寄存器在 O(n lg n/lg k) 时间内对 n 个数字进行排序。
这就是问题。我是通过分而治之的想法做到的。我认为它类似于mergesort。但是，我只能得到一个 O(n lg n/k) 的算法。在大多数情况下，O(n lg n/k) 比 O(n lg n/lg k) 慢，所以我想知道我该如何思考这个问题。谢谢。
最佳答案
通常情况下，将 K 个排序列表与总共 N 个元素合并需要 O(N log K) 时间，使用这样的算法将输入列表保存在优先级队列中并重复从所有头项中挑选最小的元素: https://www.geeksforgeeks.org/merge-k-sorted-arrays/
您的魔法寄存器组让您可以在 O(N) 时间内完成 K 路合并。您可以通过使用该功能实现合并排序来获得您想要的结果，但不是在每个级别进行 2 路合并，而是在每个级别进行 K 路合并:
- 在 O(N) 总时间内对所有长度为 K 的子列表进行排序
- 在 O(N) 总时间内将每组 K 列表合并成一个长度为 K^2 的列表
- 与创建长度为 K^3 等的列表相同。
排序每层需要 O(N) * log_k(N) 层，总共需要 O(N log_k(N)) = O(N log(N)/log(K)) 时间
关于算法:得到一个 O(n lg n/lg k) 算法而不是 O(n lg n/k)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/52744975/