整列済みの列の末尾から比較して、次の要素の挿入位置を決める単純挿入整列法について考える。
昇順に整列済みの大きさn のデータ列を、改めて昇順に整列する処理を行う場合の比較回数のオーダは、どれか。
ア | n |
イ | n2 |
ウ | logn |
エ | n logn |
答え ア
【解説】
データ数n のデータ列に対し、単純挿入整列法で要素(データ)の追加を行うときの比較回数は、最小で1、最大でn であり、平均値としては(n +1)/2になる。
この場合のオーダ(計算量)は
O (n )=n
(ア)である。
※『O (n )=n 』は計算量がn に比例するということである。
【キーワード】
・オーダ