0

結果の膨大なコレクションで解決策を探すという、非常に難しい問題 (おそらく NP 困難な問題 ^^) があります。そのためのアルゴリズムがあるのか​​もしれません。

以下の演習は人工的ですが、私の問題を説明するのに最適な例です。

整数を持つ大きな配列があります。100.000 個の要素があるとしましょう。

int numbers[] = {-123,32,4,-234564,23,5,....}

この配列の任意の 2 つの数値の合計が 0 に等しいかどうかを比較的迅速に確認したいのです。つまり、配列に "-123" がある場合、"123" もあるということです。

最も簡単な解決策は力ずくです-すべてをすべてチェックしてください。これにより、100.000 x 100.000 という大きな数値が得られます ;-) 明らかに、力ずくの方法は最適化できます。番号を注文し、ネガをポジティブのみに対してチェックします。私の質問は、解決策を見つけるために最適化されたブルートフォースよりも優れたものはありますか?

4

4 に答える 4

4

まず、配列を値の大きさでソートします。

次に、データに目的の条件を満たすペアが含まれている場合、配列内で隣接するそのようなペアが含まれています。したがって、合計が 0 である隣接するペアを探すだけです。

全体的な時間の複雑さはO(n log n)並べ替えのためのものであり、O(n)比較だけに基づいていない「不正行為」並べ替えを使用する場合に発生する可能性があります。明らかに、線形時間よりも短い時間で実行することはできません。最悪の場合、すべての要素を確認しないと実行できないためです。コンピューティングの決定木モデルではおそらく最適だと思いますn log nが、要素の一意性の問題に「少し似ている」ためです。

代替アプローチ:

要素を 1 つずつハッシュ ベースまたはツリー ベースのコンテナーに追加します。各要素を追加する前に、そのネガが存在するかどうかを確認してください。もしそうなら、やめてください。

これは、データ全体をソートするコストを節約できるため、適切なペアが多数ある場合に高速になる可能性があります。とはいえ、データのサブセットが最終的な順序になるとすぐに隣接するペアをチェックすることで、早期に終了する変更された並べ替えを作成できますが、それは努力です。

于 2012-10-10T16:16:31.257 に答える
3

ブルートフォースはO(n^2)解決策になります。あなたは確かにもっとうまくやることができます。

頭のてっぺんから、まずそれを並べ替えます。ヒープソートの複雑さはO(nlogn).

さて、最初の要素、たとえば については、 のようなa要素を見つける必要があることがわかっています。これは、バイナリ検索を使用して見つけることができます (配列がソートされているため)。二分探索の複雑さは.ba+b = 0O(logn)

これにより、O(nlogn)複雑さの全体的な解決策が得られます。

于 2012-10-10T16:16:49.597 に答える
2

あなたが提供した例は、時間内に力ずくで解決できますO(n^2)。

O(n·logn)小さい方から大きい方へ番号 ( ) を並べ始めることができます。1 つのポインターを先頭 (「最も負の数」) に配置し、別のポインターを最後 (「最も正の数」) に配置する場合O(n)、次の手順に従って、追加の手順でそのような数値のペアがあるかどうかを確認できます。

  • 両方のポインターの数値が同じモジュールを持っている場合、解決策があります
  • そうでない場合はモジュールの大きい方の数のポインタを「ゼロ」方向に動かします（マイナス側のポインタなら増やし、プラス側のポインタなら減らします）。
  • 解決策が見つかるまで、またはポインターが交差するまで繰り返します。

全体の複雑さはO(n·logn)+O(n) = O(n·logn)です。

于 2012-10-10T16:22:40.230 に答える
0

を使用して配列をソートしますQuicksort。positiveこれが起こった後、2 つのインデックスを使用して、それらを と と呼びましょうnegative。

positive <- 0
negative <- size - 1

while ((array[positive] > 0) and (array(negative < 0) and (positive >= 0) and (negative < size)) do
    delta <- array[positive] + array[negative]
    if (delta = 0) then
        return true
    else if (delta < 0) then
        negative <- negative + 1
    else
        positive <- positive - 1
    end if
end while
return (array[positive] * array[negative] = 0)

0 が配列の一部である場合にアルゴリズムが何をすべきかについて、あなたは言いませんでした。この場合、true が返されるべきだと思いました。

于 2012-10-10T16:26:46.057 に答える