データ数 n の配列をソートするアルゴリズムにおいて,時間計算量が O(nlogn) となる場合として,最も適切なものはどれか。
① 最悪計算時間でクイックソートする場合
② 最悪計算時間でマージソートする場合
③ 最良計算時間で単純挿入ソートする場合
④ 平均計算時間でシェルソートする場合
⑤ 平均計算時間で選択ソートする場合
答え
②
解説
① 最悪計算時間でクイックソートする場合
クイックソートの最悪の計算時間量は,O(n2) になるため,不適切です。
尚,平均の計算時間量はO(nlogn)です。
② 最悪計算時間でマージソートする場合
適切です。
③ 最良計算時間で単純挿入ソートする場合
単純挿入ソートの最良の計算時間量は,O(n) になるため,不適切です。
④ 平均計算時間でシェルソートする場合
シェルソートの平均の計算時間量は,O(n1.25) になるため,不適切です。
⑤ 平均計算時間で選択ソートする場合
選択ソートの平均の計算時間量は,O(n2) になるため,不適切です。