16

この質問に対する回答で、ジョン・フェミネラは次のように述べています。

各整数をビットベクトルとして表し、高速フーリエ変換を実行することで、本当に凝った場合、これを準二次的に行うことは可能ですが、それはこの回答の範囲を超えています。

その質問で説明されている問題を解決するための漸近的に最適な方法は何ですか?

4

1 に答える 1

13

配列があるとし1 2 4ます。この配列を多項式として表しf(x) = x^1 + x^2 + x^4ます。f(x)^2を見てみましょう。

x^2 + 2 x^3 + x^4 + 2 x^5 + 2 x^6 + x^8

n配列の 2 つの要素の和として記述する方法の数は の係数でx^nあり、これは一般に当てはまります。FFT は多項式を効率的に乗算する方法を提供してくれるので*、基本的に行うことはf(x)^3、ターゲット数 S の係数を計算して調べることです。

  • このアルゴリズムが 3SUM 問題を解決しない理由は、FFT 乗算の効率が結果の多項式の次数に依存し、配列値が小さな範囲にあるためです。
于 2011-07-15T01:31:21.627 に答える