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