平成20年 秋期 ソフトウェア開発技術者 午前 問11

整列済みの列の末尾から比較して、次の要素の挿入位置を決める単純挿入整列法について考える。
昇順に整列済みの大きさn のデータ列を、改めて昇順に整列する処理を行う場合の比較回数のオーダは、どれか。

 ア  n
 イ  n2
 ウ  logn
 エ  n logn


答え ア


解説
データ数n のデータ列に対し、単純挿入整列法で要素(データ)の追加を行うときの比較回数は、最小で1、最大でn であり、平均値としては(n +1)/2になる。
この場合のオーダ(計算量)は
 O (n )=n
(ア)である。

※『O (n )=n 』は計算量がn に比例するということである。


キーワード
・オーダ

キーワードの解説

戻る 一覧へ 次へ