2

私は big-O 表記法を使用してアルゴリズムのランタイムを決定する方法に比較的慣れていないため、ソート アルゴリズムのランタイムに関して質問があります。配列にペア (a, b) のセットがあり、O(n log n) で実行される既知の並べ替えアルゴリズムを使用してデータを並べ替えたとします。次に、いくつかの n 個のデータ ポイントのサブセットを取得し、そのサブセットに対して同じ並べ替えアルゴリズムを実行します (したがって、理論的には、配列全体を 2 回並べ替えることができます。最初の並べ替えは a を比較し、2 番目のセットは b を比較します)。 . つまり、私のコードは

pairArray[n];
Sort(pairArray); //runs in O(n log n)

subsetArray[subset]; //where subset <= n
for (int i = 0; i < subset; i++) {
   subsetArray[i] = pairArray[i];
}

Sort(subsetArray) //runs in O(n log n)

このコードの実行時間はまだ O(n log n) ですか? 2 つの質問があると思います: O(何か) ソートを 2 回実行すると、元の「何か」から複雑さが増しますか? 別の配列に再割り当てする反復により複雑さが増しますか? 反復はポインターで排除できるため、最初のものの方が心配です。

4

1 に答える 1

4

big-O表記では、コンスタクトファクターは無視されます。2回の並べ替えは、引き続きO（n log n）です。

実行している割り当てのループはO（n）操作です。これも無視されます。big-O表記では、最大の用語のみが言及されています。

2つのアルゴリズムのどちらが優れているかを判断したいが、それらのbig-Oが同じである場合は、現実的なデータのパフォーマンス測定を使用できます。実際のパフォーマンスを測定すると、あるアルゴリズムが通常、別のアルゴリズムの2倍遅いかどうかを確認できます。これは、big-O表記からはわかりません。

于 2012-10-06T06:28:25.513 に答える