技術士試験ナビ

技術士試験対策・テキスト・過去問題解説を発信します。

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

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

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

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

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

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

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

 

 

答え

      ②

解説

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

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

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

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

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