我正在做家庭作业，作为“提示”，我们被告知要找到以下算法，然后证明它是必要的答案。
令 L(1), L(2), .., L(k) 分别为 n 个元素的排序列表。给出一个O(kn logk)空间的算法，支持O(log n + t)的定位操作，返回t项的位置。
理想情况下，我将能够使用此算法让我对实现更好的解决方案有一些了解(这是作业想要的)，但这种效率较低的算法应该会激发我的灵感，但我想不通出去。任何想法或知道这个算法是什么？谢谢!
最佳答案
你用谷歌搜索过 O(kn logk) 吗？这似乎是一个非常独特的大 O 签名。
这是我的第一个结果: 合并排序 --> What is the relation between merges and number of items in a in k-way merge
关于algorithm - 你能帮我弄清楚这个算法吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/770571/