挿入整列の比較回数と計算量のオーダーを求める

解説

この関数は挿入ソートである。外側の for ループで i = 2 から n まで繰り返し、各回で data[i] を適切な位置に挿入する。 【n = 5、最悪の場合のトレース】 配列が降順 {5, 4, 3, 2, 1} のとき、毎回 while ループが最後まで回る。 ・i = 2: tmp = 4、j は 1 → 0 まで動く。data[1] > tmp の比較 1 回。 ・i = 3: tmp = 3、j は 2 → 0 まで動く。比較 2 回。 ・i = 4: tmp = 2、j は 3 → 0 まで動く。比較 3 回。 ・i = 5: tmp = 1、j は 4 → 0 まで動く。比較 4 回。 合計: 1 + 2 + 3 + 4 = 10 回（a = 10）。 【一般の n での最悪オーダー】 最悪の場合の比較回数は Σ(i − 1)（i = 2 から n）= 1 + 2 + … + (n − 1) = n(n − 1)/2 である。 これは n² に比例するため、オーダーは O(n²)（b = O(n²)）。 【誤答の解説】 ・ア、イ: 比較回数 4 は外側ループの繰返し回数 n − 1 であり、内側ループの比較を数えていない。 ・ウ: 比較回数 10 は正しいが、O(n) は誤り。n(n − 1)/2 は O(n²) である。 ・エ: O(n log n) はマージソート等の計算量であり、この挿入ソートには当てはまらない。 ・カ: 比較回数 16 は (n − 1)² の値で、内側ループが常に n − 1 回回ると誤解した結果。実際は i − 1 回である。

選択肢ごとの解説

ア

外側の for ループの回数（n − 1 = 4）だけを数え、内側の while ループを無視した誤り。オーダーも外側ループだけで O(n) としている。

イ

比較回数を外側ループの回数 n − 1 = 4 と誤って数えたが、オーダーは内側ループの存在から O(n²) と正しく判断した場合の誤答。

ウ

具体的な比較回数は正しく求められたが、n(n − 1)/2 のオーダーを最高次の n だけ見て O(n) と判断した誤り。

エ

具体的な比較回数は正しく求められたが、オーダーをマージソートなどの効率的な整列アルゴリズムと混同して O(n log n) とした誤り。

オ

正解。逆順の配列で比較回数は 1 + 2 + 3 + 4 = 10 回となり、一般の n では n(n − 1)/2 = O(n²) である。

カ

内側の while ループが毎回 i − 1 回ではなく常に n − 1 回実行されると誤解し、(n − 1) × (n − 1) = 16 と計算した誤り。オーダーは結果的に同じだが具体値が異なる。

登録すると解いた結果が残り、間違えた問題は日をおいて復習に出ます。