Tim*_*mmy 7 language-agnostic sorting algorithm performance search
我正在研究一种可以处理大量项目的排序/排序算法,我需要以有效的方式实现以下算法才能使其工作:
有两个数字列表.它们同样长,约100-500万件.从这里我需要找到这些列表之间的第n大产品,即.如果您创建一个矩阵,其中顶部有一个列表,那么您有另一个列表,每个单元格是上面的数字和侧面的数字的乘积.
示例:列表是A=[1, 3, 4]和B=[2, 2, 5].那么产品就是[2, 2, 5, 6, 6, 15, 8, 8, 20].如果我想要第三大,那就是8.
天真的解决方案是简单地生成这些数字,对它们进行排序然后选择第n个最大数字.但那就是O(m^2 * log m^2)m是小列表中元素的数量,而这个数字还不够快.
我认为我需要的是先对两个小清单进行排序.那是O(m * log m).然后我肯定知道最大的一个A [0]*B [0].第二大的是A [0]*B [1]或A [1]*B [0],......
我觉得这可以O(f(n))分步进行,与矩阵的大小无关.但我无法找到一种有效的方法来完成这一部分.
编辑:有一个被删除的答案,建议记住两个有序集合中的位置,然后查看A [a]*B [b + 1]和A [a + 1]*B [b],返回更大的一个并递增a/b.我会在删除之前发布此评论:
这不行.想象一下两个列表A = B = [3,2,1].这将给你像[9,6,3; 6,4,2; 3,2,1].所以你从(0,0)= 9开始,转到(0,1)= 6然后选择是(0,2)= 3或(1,1)= 4.但是,这将错过(1,0)= 6,这比两者都大.所以你不能只看两个邻居,但你必须回溯.
我认为可以在 中完成O(n log n + n log m)。这是我的算法的草图，我认为它会起作用。有点粗糙。
O(m log m)）O(m log m)）s这样吧min(m, n)。（需要O(1)）s惰性序列迭代器。 将迭代值, , ..., 。（需要）L[0]L[s-1]L[i]sA[i]*B[0]A[i]*B[1]A[i]*B[s-1]O(s)q。迭代器将根据其当前值确定优先级。（O(s)因为最初它们已经按顺序排列）n值q。最后提取的值将是所需的结果。当迭代器被拉出时，它会被重新插入，q并使用其下一个值作为新的优先级。如果迭代器已耗尽，请勿重新插入它。（需要O(n log s)）总之，该算法将采用O(m log m + (s + n)log s)，但s等于m或n。