时间戳

首页 > 解决方案 > 算法：得到一个 O(n lg n/ lg k) 算法而不是 O(n lg n/k)

algorithm - 算法：得到一个 O(n lg n/ lg k) 算法而不是 O(n lg n/k)

问题描述

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

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

这就是问题。我通过使用分而治之的想法来做到这一点。我认为它类似于mergesort。但是，我只能得到一个 O(n lg n/k) 的算法。在大多数情况下，O(n lg n/k) 比 O(n lg n/ lg k) 慢，所以我想知道我该如何思考这个问题。谢谢。

标签： algorithm

解决方案

通常，使用这样的算法将 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)) 时间

推荐阅读