以递增的顺序迭代成对的数字

Question

我将在底部解释问题的来源,但这是声明.假设我有两个非负整数列表,我将编写(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度项等等.当前的代码通过对其进行半心半意的刺激以提高效率来避免解决这个问题,然后做一个一类通用多项式加法,以按照它不期望的顺序处理系数.我觉得我们应该做得更好!

Answer 1

这个问题只是表面上与排序X + Y不同,这是多年来对计算几何学的主要刺激因素.(参见Joseph O'Rourke的(开放)问题41.)总结实施者的链接,只能添加和比较指数的最快的已知算法是O(mn log(mn)),这是显而易见的算法.如果指数是有界整数,那么彼得的傅立叶方法适用.很多聪明的人已经考虑过这个问题很长一段时间了,所以我不希望很快就会有更好的算法.

Answer 2

我想知道你的多项式有多稀疏？

对于密集多项式的乘法而言可能值得考虑的一个选项是计算多项式的傅里叶变换并将它们的傅立叶系数相乘.

这允许您在O(nlogn)中乘以多项式,其中n是多项式的次数.

这对于诸如(1 + x ^ 1000000)*(1 + x ^ 1000000)的稀疏多项式是不合适的,因为n将是大约1000000,而当前算法将仅需要几个周期.

在这些讲义中可以找到这种傅立叶方法的一个很好的解释.

Answer 3

据我所知,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

现在对于每一行,左边的对应总是在右边的对之前被拾取.

1. 所以第一个候选人是a1b1.
2. 然后一旦a1b1被选中,接下来的候选人就是a1b2和a2b1.
3. 说a1b2得到挑选.然后候选人是a1b3和a2b1.
4. 现在说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.