部分和問題がわかりません。

部分和問題がわかりません。

[問題]
n個の整数が配列Aに格納されていて、整数xの値を与えたときに、
A[i] + A[j] = x
となるi,jが存在するかどうかを判定する、なるべく効率のよいアルゴリズムを示せ。

この問題は部分和問題のため、NP完全問題なので、総当たりのO(n^2)より効率のいい方法がないと思うのですが、もっと効率のよい方法が存在するのでしょうか？

No.2 ベストアンサー 回答者： bug_bug 回答日時： 2010/02/11 19:43

フォントによっては見難いですが アイ　と　ジェー　ですね.

与えられた命題にこっそり隠されているヒント(条件)を見つけましょう
ポイントは
(1) "整数"と条件があること. 負数は含まれません.
(2) "加算"のみであること. A[i] > x ならどんな整数を加算しても条件を満たしません.

付け加えるならば,
(3) "存在するかどうかを判定する"のみで要素番号を示す必要はありません.

以上から
・配列Aをソートし配列aとする. ※ポイント(3)
・二分探索を用いてa[k] < xを満たすkを探す. ※ポイント(2)
・二分探索を用いてa[l] < x - a[k] を満たすlを探す
・HITしたら処理終了 ※ポイント(3)

もっと良いアルゴリズムもあるかもしれませんが、
ざっくりとO(n^2)よりO(log2n)を使える状態にしたほうが効率は良いでしょう.

さらに正解に近づけるためにはソートに掛かるコストも算出し,
処理効率が切り替わるnの値も出す必要があるでしょう.

No.5 回答者： beefisdead 回答日時： 2010/02/14 15:15

いかにもレポートや宿題のように見えるのであまり詳しい話は避けているのですが、自然数だけだと勘違いをしていましたので、補足です。

A[i]が自然数という前提なら、x個のバケツを用意すれば一回なめるだけでOKです。

A[i]が整数でも、自然数に変換してからバケツを用意すれば同じアルゴリズムが使えますので、これまたO(n)です。
ただ、メモリが確保出来るとは限らないので、実際はこの手段は取れません。ツリーかハッシュテーブルを作ることになります。
ハッシュテーブルの探索挿入は一応O(1)と言われているので、（やや回りくどいですが）これまた O(n) と言えないこともないでしょう。

No.4 回答者： Tacosan 回答日時： 2010/02/13 01:25

まずこの問題は「部分和問題」ではありません. そして, 「NP完全問題なので、総当たりのO(n^2)より効率のいい方法がないと思う」も間違い. NP完全なら O(n^2) はありえないし, NP完全であっても「総当たりより効率のいい方法がない」とも限りません.

さておき, 今は加えるのが 2個に限定されてますから,
A[i] + A[j] = x iff (A[i]+M) + (A[j]+M) = x+2M
です. つまり, A[i] は全て正と仮定してもかまいません＞#3. あと, ソートしたあとは O(n) でできます. どうせソートしてるので O(n log n) であることに変わりありませんが.
全体で O(n) は無理な気がするけどどう示すんだろう?

No.3 回答者： bug_bug 回答日時： 2010/02/11 19:55

ど勘違いしてました.

整数ですので負数が含まれますね.

手順はさほど変わりませんが負数をケアする必要があります
・配列Aをソートし配列aとする.
・最小値a[k]を二分探索.
・a[k]が負数の場合, a[l] > a[k]となるlを二分探索.
・a[k]が整数の場合, a[l] < x - a[k] となるlを二分探索.

お恥ずかしい・・・

No.1 回答者： beefisdead 回答日時： 2010/02/11 15:34

二つの合計だけを判定するなら、x個のバケツを用意して順次突っ込んでいけば、O(n)で済むように思えますね。

問題としては、
A[i] == A[j] となる組み合わせを探すアルゴリズムを答えよ
と変わりないですよね。