讨论一个算法有关问题的优化

讨论一个算法问题的优化
给定两个有序正整数数组a,b，长度都为n（n大概在20k~200k左右）。要找i,j,k使得a[i]+a[j]=b[k]。只求速度最快。优化复杂度最好，优化常数也行。
我现在是O(n^2)的。
for(i=0,k0=0;i<n;i++)
{
  while(b[k0] < a[i]) k0++;
  for(j=i,k=k0;j<n;j++)
  {
    while(b[k] < a[i] + a[j]) k++;
    if(b[k] == a[i] + a[j]) return result;
  }
}

实际数据的话a,b都是__uint128_t。最后是要在3930上跑，可以12线程。但是n>64k的时候会爆L3（32*200k=6.4M>2M）。所以如果能优化成方便多线程并且cache friendly的话最好。
[解决办法]

引用:

常数？
C/C++ code1while(b[k0] < a[i]) k0++;
改成
C/C++ code1while(b[k0] < a[i]*2) k0++;

还有怎么看都是O(n^3)的复杂度啊。。。

看错了，是平方级的。那么内层循环结束条件是j<n&&k<n...
按说寻找下一个k时是能二分的，但估计还不如直接扫来的快，对复杂度也没什么帮助
[解决办法]
期望这么低的话，是不是无解判断也挺重要的？
有个常数级的小优化就是，只用Int32来算，如果Int32中找到了，再到Int128中验证，不知这样减少数据量对缓存是否有些好处。

引用:

只要找到一个就可以。找到所有的我觉得也差不到哪里去。我的数据是期望找到0个解的。

[解决办法]

引用:

期望这么低的话，是不是无解判断也挺重要的？
有个常数级的小优化就是，只用Int32来算，如果Int32中找到了，再到Int128中验证，不知这样减少数据量对缓存是否有些好处。

2^(15*3)=2^45，感觉int32冲突概率好大，至少得用int64验证。

a[i]+a[j]=b[k]=M-a[n-1-k]
=>a[i]+a[j]+a[k1]=M
=>(a[i]-M/3)+(a[j]-M/3)+(a[k1]-M/3)=M-(M/3*3)
我的理解是，等价于在a中找3个数使它们的和为M。
将a[i]-M/3，使得M=0/1/2，a分为正(V)负(S)两部分。
如果k1<>i/j那么有三种情况：
1.一正两负，这个验证是O(V*S)
2.两正一负，这个验证是O(V*S)
3.三正，这个验证应该是O(1)的
如果k1==i/j，这两种情况的验证都是O(n)。
我想的就这样，不知道又没有问题。

查看更多 下一篇