整列済みの列の末尾から比較して、次の要素の挿入位置を決める単純挿入整列法について考える。
昇順に整列済みの大きさn のデータ列を、改めて昇順に整列する処理を行う場合の比較回数のオーダは、どれか。
| ア | n | イ | n2 | ウ | logn | エ | n logn |
答え ア
【解説】
データ数n のデータ列に対し、単純挿入整列法で要素(データ)の追加を行うときの比較回数は、最小で1、最大でn であり、平均値としては(n +1)/2になる。
この場合のオーダ(計算量)は
O (n )=n
(ア)である。
※『O (n )=n 』は計算量がn に比例するということである。
【キーワード】
・オーダ
- オーダ(計算量)
コンピュータの処理時間を考えた場合、最も正確に測定する方法は実際にプログラムを作って実機で処理時間を計測する方法であるが、プログラムの設計段階で2つのアルゴリズムの計算時間を比較する場合には、プログラムを作って比べることは難しいため、各アルゴリズムの計算量を調べて、計算量で比較を行います。
一般にコンピュータの処理で時間がかかるのは、比較演算であるので計算量を考えるときは、そのアルゴリズムの比較演算の回数を用います。
計算量を表す記号はオーダ(程度)を意味するO ( )を使用します。
もっと、「計算量」について調べてみよう。
戻る
一覧へ
次へ