技術士第一次試験専門科目 平成28年度 Ⅲ-5

　データ数 n の配列をソートするアルゴリズムにおいて，時間計算量が O(nlogn) となる場合として，最も適切なものはどれか。

①　最悪計算時間でクイックソートする場合

②　最悪計算時間でマージソートする場合

③　最良計算時間で単純挿入ソートする場合

④　平均計算時間でシェルソートする場合

⑤　平均計算時間で選択ソートする場合

答え

      ②

解説

①　最悪計算時間でクイックソートする場合
クイックソートの最悪の計算時間量は，O(n²) になるため，不適切です。
尚，平均の計算時間量はO(nlogn)です。

②　最悪計算時間でマージソートする場合
適切です。

③　最良計算時間で単純挿入ソートする場合
単純挿入ソートの最良の計算時間量は，O(n) になるため，不適切です。

④　平均計算時間でシェルソートする場合
シェルソートの平均の計算時間量は，O(n^1.25) になるため，不適切です。

⑤　平均計算時間で選択ソートする場合
選択ソートの平均の計算時間量は，O(n²) になるため，不適切です。