5

私は行列m * nを持っており、各行について、それらの間のすべての要素を比較する必要があります。見つけたカップルごとに、計算を実行する関数を呼び出します。

例：

my_array -> {1, 2, 3, 4, 5, ...}

I take 1 and I have: (1,2)(1,3)(1,4)(1,5)
I take 2 and I have: (2,1)(2,3)(2,4)(2,5)
and so on

CI を使用すると、次のように記述されます。

for (i=0; i<array_length; i++) {
    for (k=0; k<array_length; k++) {
        if (i==k) continue;

           //Do something
        }
    }
}

複雑さの低いアルゴリズムを使用できるかどうか疑問に思っていました。

4

3 に答える 3

5

いいえ、それは定義上 O(n^2) です [ここで説明するには長すぎますが、私を信じてください (-: ])。
ただし、反復回数を半分に減らすことができます。

for (i=0; i<array_length; i++) {
    for (k=i+1; k<array_length; k++) { // <-- no need to check the values before "i"
           //Do something
           //If the order of i and k make a different then here you should:
           //'Do something' for (i,k) and 'Do something' for (k,i)
        }
    }
}
于 2013-03-28T12:28:45.153 に答える
3

実行できることはいくつかありますが、それらは可能であり、配列の性質と適用する式に依存しません。式がその引数に依存する複雑さを持っていない限り、計算を高速化できたとしても、全体的な複雑さはおそらく変わらないか、増加することさえあります。

また、 B が A よりも十分に小さい場合、b > a (複雑度が高い) でAO(N^a) から BO(N^b) に移行することは、N のある範囲で、追求する価値があります。

順不同：

  • マトリックスに繰り返し項目がいくつかある場合は、キャッシュ関数を使用すると便利です。

    結果関数 (引数 1、引数 2) { int i = インデックス (引数 1、引数 2); // 値によっては、 // arg1*(MAX_ARG2+1) + arg2; のようになります。if (!stored[i]) { // 格納され、値が割り当てられ、 // 別の場所で初期化されます。 // 静的フラグを使用してこの関数内で。保存された[i] = 1; 値[i] = true_function(arg1, arg2); 戻り値[i]; }

    次に、使用可能な値の異なるペアの数に比例するメモリ オーバーヘッドがあります。呼び出しのオーバーヘッドは O(|arg1|*|arg2|) になる可能性がありますが、状況によっては (たとえばtrue_function()、コストがかかる場合)、節約によって追加された複雑さが相殺されます。

    • 数式を細かく切り刻み (すべての数式で可能というわけではありません)、次のように表します。

      F(x,y) = G(x) op H(y) op J(x,y)

    次に、G[] と H[] を事前に計算する O(max(M,N)) サイクルを実行できます。これには O(M+N) のメモリ コストもかかります。F と J の計算コストの差が大きい場合にのみ便利です。または、次のようにすることもできます。

    for (i in 0..N) {
    g = G(array[i]);
    for (j in 0..N) {
        if (i != j) {
            result = f(array[i], array[j], g);
        }
    }
}

    これにより、複雑さの一部が O(N^2) から O(N) に低下します。

    • 最初の 2 つの手法は、G() または H() をキャッシュするのが実用的である場合 (引数の範囲が制限されている、高価な関数)、併用できます。

    • F(a, b) と F(a+c, b+d) を結び付ける「法則」を見つけます。その後、同じ計算を再利用して、キャッシュ アルゴリズムをより効率的に実行できます。これにより、一部の複雑さが O(N^2) から O(N) または O(log N) にシフトするため、全体的なコストは依然として 2 次ですが、成長ははるかに遅くなり、N の上限が実用的になります。F 自体が (a,b) の定数よりも高次の複雑さである場合、これによりこの次数も減少する可能性があります (極端な例として、F が a および/または b で反復的であるとします)。

于 2013-03-28T13:36:58.337 に答える
2

いいえ、配列の内容の知識と、アルゴリズムを最適化するための操作のセマンティクスを含める場合にのみ、計算の複雑さを軽減できます。

于 2013-03-28T12:24:25.993 に答える