I'm working on a homework assignment and as a "hint" we are told to find the following algorithm, and then prove it to the necessary answer.
我正在做一个家庭作业,作为一个“提示”,我们被告知找到以下算法,然后证明它是必要的答案。
Let L(1), L(2), .., L(k) be sorted lists of n elements each. Give a O(kn logk) space algorithm that supports the O(log n + t) Locate operation, which returns the location of t items.
设L(1),L(2),...,L(k)为每个n个元素的排序列表。给出O(kn logk)空间算法,该算法支持O(log n + t)Locate操作,该操作返回t项的位置。
Ideally, I will be able to use this algorithm to give me some insight into achieving a better solution (which is what the assignment wants), but this less effecient algorithm is supposed to inspire me, but I can't figure it out. Any thoughts or know what this algorithm is? Thanks!
理想情况下,我将能够使用这个算法给我一些洞察力来实现更好的解决方案(这是任务所需要的),但这种效率较低的算法应该激励我,但我无法弄清楚。有什么想法或知道这个算法是什么?谢谢!
6 个解决方案
#1
Have you googled for O(kn logk) ? That seems to be a pretty unique big-O signature.
你用Google搜索了O(kn logk)吗?这似乎是一个非常独特的大O签名。
Here's my first result: MergeSort --> What is the relation between merges and number of items in a in k-way merge
这是我的第一个结果:MergeSort - >合并与k-way合并中的项目数之间的关系是什么
#2
I can't seem to find one that gives O(log n + t) time, but I had a thought that might or might not help...
我似乎无法找到一个给出O(log n + t)时间的东西,但我有一个想法可能会或可能没有帮助......
O(kn log k) is the size of a table mapping each possible item to the number of the list containing it. However, using that to find which list to look in still results in a t*O(log n)-lookup time for t elements, so it's not really what's asked for...
O(kn log k)是将每个可能项目映射到包含它的列表编号的表格的大小。但是,使用它来查找要查找的列表仍会导致t元素的t * O(log n) - 查找时间,因此它并不是真正要求的...
#3
Probably not a sorting function since you already have 2 sorted lists. Sounds like Binary Search to me as well.
可能不是排序功能,因为您已经有2个排序列表。听起来像二元搜索我也是。
#4
I think it asks you to find an inefficient algorithm first, then use that to make an efficient one. It sounds like a linear search of lists, each with a binary search to look through them. It will require O(2t) space, because you need to copy down the "coordinates" of the t items.
我想它首先要求你找到一个效率低下的算法,然后用它来制作一个有效的算法。这听起来像是列表的线性搜索,每个列表都有一个二进制搜索来查看它们。它需要O(2t)空间,因为你需要复制t项的“坐标”。
#5
Even with that ugly big O notation I think it's a Binary Search problem because you have the sorted lists.
即使有那个丑陋的大O符号,我认为这是一个二进制搜索问题,因为你有排序列表。
Space complexity remains the same because it's a divide and conquer algorithm,so you won't have problems there.
空间复杂性保持不变,因为它是一种分而治之的算法,所以你不会遇到问题。
To be very sure is the t outside the logn, something like O((logn)+t)?
非常确定是否在log外面,就像O((logn)+ t)?
#1
Have you googled for O(kn logk) ? That seems to be a pretty unique big-O signature.
你用Google搜索了O(kn logk)吗?这似乎是一个非常独特的大O签名。
Here's my first result: MergeSort --> What is the relation between merges and number of items in a in k-way merge
这是我的第一个结果:MergeSort - >合并与k-way合并中的项目数之间的关系是什么
#2
I can't seem to find one that gives O(log n + t) time, but I had a thought that might or might not help...
我似乎无法找到一个给出O(log n + t)时间的东西,但我有一个想法可能会或可能没有帮助......
O(kn log k) is the size of a table mapping each possible item to the number of the list containing it. However, using that to find which list to look in still results in a t*O(log n)-lookup time for t elements, so it's not really what's asked for...
O(kn log k)是将每个可能项目映射到包含它的列表编号的表格的大小。但是,使用它来查找要查找的列表仍会导致t元素的t * O(log n) - 查找时间,因此它并不是真正要求的...
#3
Probably not a sorting function since you already have 2 sorted lists. Sounds like Binary Search to me as well.
可能不是排序功能,因为您已经有2个排序列表。听起来像二元搜索我也是。
#4
I think it asks you to find an inefficient algorithm first, then use that to make an efficient one. It sounds like a linear search of lists, each with a binary search to look through them. It will require O(2t) space, because you need to copy down the "coordinates" of the t items.
我想它首先要求你找到一个效率低下的算法,然后用它来制作一个有效的算法。这听起来像是列表的线性搜索,每个列表都有一个二进制搜索来查看它们。它需要O(2t)空间,因为你需要复制t项的“坐标”。
#5
Even with that ugly big O notation I think it's a Binary Search problem because you have the sorted lists.
即使有那个丑陋的大O符号,我认为这是一个二进制搜索问题,因为你有排序列表。
Space complexity remains the same because it's a divide and conquer algorithm,so you won't have problems there.
空间复杂性保持不变,因为它是一种分而治之的算法,所以你不会遇到问题。
To be very sure is the t outside the logn, something like O((logn)+t)?
非常确定是否在log外面,就像O((logn)+ t)?
#6
ehh... sounds like... binary search? Wiki
呃......听起来像......二元搜索?维基