出典：公益社団法人 日本技術士会「技術士第一次試験 過去問題」
データ数nの配列をソートするアルゴリズムで、時間計算量がO(n log n)となる場合として、マージソートの最悪計算時間などを選択肢から選ぶ問題。
各ソートアルゴリズムの最悪・平均計算時間から、O(n log n)となるものを選ぶ問題。
① 覚える: マージソートは最悪でもO(n log n)。挿入・バブル・選択ソートはO(n²)。クイックソートは平均O(n log n)だが最悪O(n²)
② O(n log n)になるのはマージソートの最悪計算時間だけ
③ ①
マージソートは、配列を半分に分割して再帰的にソートし、併合する。分割の深さがlog n、各段の併合がO(n)なので、最悪の場合でも計算時間はO(n log n)である。したがって①が最も適切である。
O(n log n)のソート: マージソート(最悪も)、ヒープソート(最悪も)、クイックソート(平均)。基本的なソート(バブル・選択・挿入)はO(n²)。
キーワード: ソートアルゴリズム、計算量、マージソート、クイックソート、O(n log n)、情報工学部門
同じ問題が計2回出題されています(令和3年度、令和6年度)。