3SUMと呼ばれる次の判定問題を考えます:
入力 : $n$個の整数値 $A=(a_1,\dots,a_n)$ ただし$a_i\in[-n^c,n^c]$.
出力 : YES iff 相異なる三つ組 $(i,j,k)$ が存在して $a_i+a_j+a_k=0$
この問題は
for i in range(n):
for j in range(n):
for k in range(n):
if a[i]+a[j]+a[k]==0: return YES
return NO
というコードによって$O(n^3)$時間で解けますが, 少し工夫して次のようにすれば $O(n^2\log n)$ 時間で解けます.
L = []
for i in range(n):
for j in range(n):
L.append(a[i]+a[j])
L.sort()
for k in range(n):
if -a[k] is in L: // 二分探索をして-a[k]がLにあるかどうかを判定
return True
return False
しかし尺取り法に基づいた次のアルゴリズムを用いると$O(n^2)$時間で解くことができます (簡単のため, 入力配列$A$の中身は全て相異なる要素であるとします).
A.sort()
for i in range(n):
l = 0
u = n-1
while True:
if u==l: return False
if A[i]+A[u]+A[l]==0: return True
elif A[i]+A[u]+A[l]>0: u-=1
elif A[i]+A[u]+A[l]<0: l+=1
3SUMという問題は計算幾何学や精緻な計算量理論において非常に重要な問題の一つとされていて, 任意の定数$\epsilon>0$に対して$O(n^{2-\epsilon})$時間では解けないと予想されています.
一方で$\mathrm{polylog}(n)$倍の改善はなされています.
