Subquadratic Algorithms for 3SUM
Subquadratic Algorithms for 3SUM
复制标题
3SUM 的次二次算法
DOI：
10.1007/s00453-007-9036-3
复制
发表时间：
2005
期刊：
影响因子：
1.1
通讯作者：
M. Patrascu
中科院分区：
文献类型：
--
作者：
Ilya Baran;E. Demaine;M. Patrascu
抽象的
我们在几个模型中获得了三个模型中的3sum的次级算法。
$（n^{2}/\ max \ {\ frac {w} {\ lg^{2} w}，\ frac {\ lg^{2} n} n} {（\ lg \ \ lg n）^{2 } \}）$
。
$ O（n^{2}/\ frac {w^{2}}} {\ lg^{2} w}）$
。
$（n^{2}/\ frac {mb} {\ lg^{2} m}）$
。
Abstract
We obtain subquadratic algorithms for 3SUM on integers and rationals in several models. On a standard word RAM with w-bit words, we obtain a running time of
$O(n^{2}/\max\{\frac{w}{\lg^{2}w},\frac{\lg^{2}n}{(\lg\lg n)^{2}}\})$
. In the circuit RAM with one nonstandard AC0 operation, we obtain
$O(n^{2}/\frac{w^{2}}{\lg^{2}w})$
. In external memory, we achieve O(n2/(MB)), even under the standard assumption of data indivisibility. Cache-obliviously, we obtain a running time of
$O(n^{2}/\frac{MB}{\lg^{2}M})$
. In all cases, our speedup is almost quadratic in the “parallelism” the model can afford, which may be the best possible. Our algorithms are Las Vegas randomized; time bounds hold in expectation, and in most cases, with high probability.