私は 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 回実行すると、元の「何か」から複雑さが増しますか? 別の配列に再割り当てする反復により複雑さが増しますか? 反復はポインターで排除できるため、最初のものの方が心配です。