n要素の配列から3要素のすべての組み合わせを見つける

Question

n要素の配列から一意の3要素のすべての組み合わせを返す最速のアルゴリズムについて考えていました。明らかなのはO（n^3）ソリューションです。これは考えられるすべての組み合わせを考慮に入れていますが、これはブルートフォースであり、私はもっと迅速に何かを見つけるつもりです。 C++で答えを探す

Answer 1

（配列のすべての項目が異なっている）あなたは出力に

n !/((n - 3)! * 3!) == n * (n - 1) * (n - 2)/6 

明確なアイテムを持っているので、O(n**3)はあなたが達成することができ、すべてのです。配列は、多くのアイテムが、いくつか明確なものを持っている場合 は、あなたがそれを前処理することができます。すべての項目ocurrenciesを削除しますが、3 ：

[0, 1, 1, 1, 1, 0, 2, 1, 2, 2, 2, 1] -> [0, 0, 1, 1, 1, 2, 2, 2] 

あなたは、配列の項目の前処理のための良好なハッシュ関数を使用している場合ステージはO(N)となります。 の場合、の場合（すべての項目が同じです）、プリプロセスにはO(N) が、唯一の回答出力はO(1)となり、 ルーチン全体ではO(N)になります。

任意の配列の場合、配列全体をスキャンする必要があるため、O(N)より複雑ではありません。プロセスがはるかに速くなります運がよけれ場合は最後に、配列の項目のための前処理との良好なハッシュ関数の場合の複雑さは

[O(N)..O(N**3)] 

の範囲です。大量のデータを出力する場合は、大きなコレクションを出力します。

Answer 2

これを行う方法はありません。あなたが何をしていても、それらの3つの要素を得る必要があるからです。サイズはnC3 = n*(n-1)*(n-2)/6です。いつでもこれを繰り返す必要があります。したがって、複雑さの最小値はO(n^3)になります。 最悪場合