Rup*_*ick 19 sorting iteration algorithm numbers
我将在底部解释问题的来源,但这是声明.假设我有两个非负整数列表,我将编写(A[0] ... A[n])和(B[0] ... B[m]).他们是严格递增的,所以A[i+1] > A[i]所有的i也是类似的B.我想n * m按照它们总和的递增顺序收集所有元素对.
所以,例如,如果A = (0 1 2)和B = (1 4),那么我想最终收集((0 1) (1 1) (2 1) (0 4) (1 4) (2 4)).如果有一个平局,我不关心我收集这两个元素的顺序.例如,如果A = (0 1)和B = (0 1),那么我不介意哪个混合术语,(0 1)或者(1 0),我先拿起.
显然,我希望这是合理有效的.我希望它有可能及时渐近m * n.具体来说,如果我对输入一无所知,我希望有序输入能使这个问题比同等问题更容易.当我第一次提出问题时,我在思考的是我们必须存储的状态量.我希望这可能是一个恒定的数额,但也许这是不现实的.(自那以后我尝试过的都失败了!)
代码实际上是用Lisp编写的,但我认为问题陈述几乎与它无关.输入最自然地会作为单链接列表,但无论如何我都必须提前撤消它们,所以如果随机访问是相关的,我可以将它们作为数组.如果它是相关的,我希望这主要是在非常小的列表上调用,因此运行时的大量常量项/常数因子可能会排除解决方案.(虽然我很想知道算法的想法!)
背景:我一直在查看Maxima的源代码,这是一个计算机代数系统,特别是它的代码,用于两个多项式的乘法.多项式以"稀疏格式"表示,因此x^5 + x^2 + 2可能显示为(5 1 2 1 0 2),下降指数后跟各自的系数.为了有效地计算产品,我真正想做的是收集零度项,然后是1度项等等.当前的代码通过对其进行半心半意的刺激以提高效率来避免解决这个问题,然后做一个一类通用多项式加法,以按照它不期望的顺序处理系数.我觉得我们应该做得更好!
这个问题只是表面上与排序X + Y不同,这是多年来对计算几何学的主要刺激因素.(参见Joseph O'Rourke的(开放)问题41.)总结实施者的链接,只能添加和比较指数的最快的已知算法是O(mn log(mn)),这是显而易见的算法.如果指数是有界整数,那么彼得的傅立叶方法适用.很多聪明的人已经考虑过这个问题很长一段时间了,所以我不希望很快就会有更好的算法.
据我所知,O(N*M)由于以下逻辑,您甚至无法希望解决方案具有复杂性.
说数组是(a1, a2, a3, a4)和(b1, b2, b3, b4, b5)
可能的对应如下:
a1b1 a1b2 a1b3 a1b4 a1b5
a2b1 a2b2 a2b3 a2b4 a2b5
a3b1 a3b2 a3b3 a3b4 a3b5
a4b1 a4b2 a4b3 a4b4 a4b5
现在对于每一行,左边的对应总是在右边的对之前被拾取.
a1b1. a1b1被选中,接下来的候选人就是a1b2和a2b1. a1b2得到挑选.然后候选人是a1b3和a2b1. a2b1得到了选择.候选人是a1b3,a2b2和a3b1.因此,我们看到随着我们前进,该职位的候选人数量呈线性增长.
因此,在最坏的情况下,你将不得不进行比较N*M*M.
一种O(N*Mlog(M*N))方法.(where N = a.size() and M = b.size())
for ( int i = 0; i < a.size(); i++ )
for ( int j = 0; j < b.size(); j++ )
sumVector.push_back( a[i] + b[j] );
sort( sumVector ); // using merge sort or quicksort.