3

ペアリング操作のbig-O表記に頭を巻くのに苦労しています。質問は非常に単純です-配列内の特定の数値リストに対して可能なすべてのペアを生成します。

私の最初の推測は、ネストされたfor / foreachループを作成し、ペアを生成することです。これは非常に簡単で、nごとに、他のn個の数値を分析すると、n^2の複雑さが得られます。

ここで、これをさらに最適化して、（1,4）が（4,1）と同じであると言うと、1,2,3,4,5のようなソートされた配列の場合です。この方法では、ネストされたforループでのみペアリング操作を実行します

for (i =0; i < count; i++) {
    for (j = i + 1; j < count - 1; j++)
    }
}

この場合、配列を<n^2回実行するだけです。7つの数値のサンプルサイズの場合、ループを21回実行して、ペアを生成しました。これはlog-n演算にはなり得ないことを知っており、この演算はn ^ 2に収束すると言いたくなりますが、数学や理論のクラスからこれに明確に答えるのに十分な記憶がありません。この問題を解決するにはどうすればよいですか？

コンテキスト：同様の質問でインタビューを行いました。これは、リストからのペアリング操作がn ^ 2よりも優れている場合、友人との議論から生まれました。

4

3 に答える 3

7

実行している操作がn2未満であることは正しいです。問題は、実行している操作がいくつ少ないかです。

配列にいくつのペアがあるかを考えてみましょう。n個の数のそれぞれが（n-1）の他の数とペアになることができる場合、可能なペアの総数はn（n-1）です。元のforループを繰り返すたびに、これらのペアの1つが生成されるため、生成するペアの総数はn 2 -n、つまりO（n 2）になります。

では、（1、4）と（4、1）が同じであると言って、重複するペアを削除するとどうなるでしょうか。この場合、生成するペアの半分は無関係になることに注意してください。各ペアを2回生成します。これは、ペアの数が（n 2 -n）/ 2であることを意味します。この式は、n 2未満ですが、big-O表記は定数を無視するため、 O（n 2 ）のままであることに注意してください。

言い換えると、生成しているペアはn 2未満ですが、作成しているペアの総数はO（n 2）のままです。

より一般的には、アルゴリズムが実行する作業の合計量を一定の係数で減らした場合（たとえば、作業を半分に削減したり、作業を100倍に削減したりした場合）、big-Oランタイムは変更されていません。アルゴリズムの。Big-Oは定数を完全に無視します。big-Oランタイムを減らすには、作業の合計量を一定よりも多く減らす必要があります。たとえば、nの係数、lognなどです。

お役に立てれば！

于 2012-04-05T22:29:15.070 に答える
0

big-O表記には、暗黙の乗法定数が含まれることに注意してください。したがって、実行時間が<= kn ^ 2 as n->無限大の場合、複雑さは依然としてO（n ^ 2）です。

于 2012-04-05T22:27:13.247 に答える
0

注文要件を導入する前のペアのちょうど半分ができたので、まだO（n ^ 2）です。2で割っても、ビッグオーは変わりません。

于 2012-04-05T22:27:50.110 に答える