1

整数 の配列が与えられ、[a1 a2 ... an]必ずしも異なるとは限りませんが、 のように異なるインデックスがある場合は "yes" を返し、そうでない場合は "no" を返すアルゴリズムを与えてください。i,j,kai + aj = ak

O（n ^ 3）かかるブルートフォースよりも速くこれを行う方法はありますか？

4

4 に答える 4

2

はいあります。

最初のステップ:配列をソートします。

次に、スマートな方法でインデックスを調べます。賢明な方法は選択することかもしれません

  • a0 + a1
  • a0 + a2
  • a0 + a3
  • ...
  • a0 + a(n-1)
  • a1 + a(n-1)
  • a1 + a(n-2)

ここでスマートとは、テストされたインデックスの 2 つの連続するペアが互いに離れすぎてはならないことを意味します。

最初のものについては、に二分探索でそのようなものaO + a1があるかどうかを調べます。ka0 + a1 = akO(logn)

次のものについては、テストされたペアが前のものに近いことを考えると、これは、そのようk'なものがあるai + aj = ak'場合、k'に近い必要があることを意味しkます。おそらく、一致するか、ペアに対して大きすぎる/小さすぎるkまで、線形検索で逃げることができます。これは、平均的なケースでコストがかかります。k'ai + ajO(1)

多くてもペアをテストする必要がn^2あるため、アルゴリズム全体はO(n^2).

于 2012-11-02T16:18:05.510 に答える
1

  • すべての可能な合計 ai + aj: O(n^2) のリストを作成します。
    リストのサイズは n^2 になります

  • 次に、そのリストを配列と比較して、類似点があるかどうかを確認します。

    • 各リストの最初のソート: O((n^2)log(n^2)) + O(nlogn)
    • それらを調べて一致するものを見つけます: O(n^2)

合計: O((n^2)log(n^2)) ( = alestanis からのコメントごとに O((n^2)log(n)))

編集:個別の要件を忘れていましたが、結果が変わることはありません。
まず、i!=j を保証するために、ステップ 1 ですべての合計のリストを作成するときに i==j を除外します。次に、
i!=k および j!=k を保証するために、各合計にそのインデックス i,j をタグ付けします。ソートする前に、元の各値にインデックス k をタグ付けします。
次に、最後のステップで一致が見つかったら、タグ付けされたインデックスが異なるかどうかを確認します。

于 2012-11-02T16:18:47.517 に答える
0 
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

bool SUM3(vector<int> &v)
{
  sort(v.begin(), v.end());

  for (int i = 0; i < v.size(); ++i) {
    int j = 0, k = v.size() - 1;

    while (j < k) {
      int result = v[j] + v[k] - v[i];

      if (result < 0 || i == j) ++j;
      else if (result > 0) --k;
      else return true;
    }
  }

  return false;
}

int main()
{
  int a1[] = {25, 7, 9, 2, 4, 8, 10};
  vector<int> v1(a1, a1 + sizeof a1 / sizeof a1[0]);

  printf("%s\n", SUM3(v1) ? "true" : "false");

  int a2[] = {1, 2, 4};
  vector<int> v2(a2, a2 + sizeof a2 / sizeof a2[0]);

  printf("%s\n", SUM3(v2) ? "true" : "false");
  return 0;
}

このアルゴリズムの複雑さはO（n ^ 2）です。

于 2012-11-02T18:00:50.653 に答える
0

次の python コードは、alestanis によって述べられた方法と同様の方法を実装し、Daniel Le によって言及されたウィキペディアの記事に示されている 2 次アルゴリズムと同様です。大きな一様乱数の正の整数の場合、記載されている O(n^2) の複雑さが保持されるようです。(k をインクリメントする内部検索ループは、平均して約 (n^2)/4 回実行されました。) 古い AMD Athlon 5000 プロセッサ上の Linux で実行された時間指定されたサンプルからの出力が最初に表示され、その後にコードが続きます。

0.002519    N 50    NN 2500     ops 607     NN/ops 4.1186   NN/t 992405.8   Matches 0
0.00752     N 100   NN 10000    ops 1902    NN/ops 5.2576   NN/t 1329794.2  Matches 0
0.035443    N 200   NN 40000    ops 10648   NN/ops 3.7566   NN/t 1128570.5  Matches 2
0.063056    N 400   NN 160000   ops 37403   NN/ops 4.2777   NN/t 2537427.4  Matches 33
0.176328    N 800   NN 640000   ops 163247  NN/ops 3.9204   NN/t 3629595.6  Matches 244
0.729919    N 1600  NN 2560000  ops 658122  NN/ops 3.8899   NN/t 3507238.7  Matches 2062
2.720713    N 3200  NN 10240000     ops 2535751     NN/ops 4.0383   NN/t 3763719.4  Matches 16178
11.07818    N 6400  NN 40960000     ops 10160769    NN/ops 4.0312   NN/t 3697358.2  Matches 128793

import random, bisect, time
V, W, N, Nlim = 500, 500000, 50, 6400
while N <= Nlim:
    t0 = time.time()
    U=sorted([random.randint(V,V+W) for i in range(N)])
    bigsum = U[-1]
    U.append(N*W)
    matches = ops = 0
    for i, ai in enumerate(U[:-2]):
        k = bisect.bisect_right(U, ai+U[i+1])
        for j, aj in enumerate(U[i+1:-1]):
            while ai+aj > U[k]:
                k += 1
                ops += 1
            if U[k] == ai+aj:
                #print 'Match', i, j, k, ai, aj, ai+aj, U[k]
                matches += 1
            if ai+aj > bigsum:
                break
    et = time.time() - t0
    print round(et,6), '\tN',N, '\tNN', N*N, '\tops', ops, '\tNN/ops',
    print round(float(N*N)/ops,4), '\tNN/t', round(N*N/et,1), '\tMatches', matches
    N *= 2

ウィキペディアの概要に従ってコードを書き直す必要があります。書き直せば、厄介な配列スライス番号と不要な完了チェックの一部がクリーンアップされる可能性があります。

于 2012-11-02T17:48:13.607 に答える