アルゴリズムの処理時間や問題の計算時間を比較するときに使用するオーダ記法の説明として、適切なものはどれか。
| ア | アルゴリズムが解に到達するまでの計算量の下限値を表す。 |
| イ | アルゴリズムがこれより遅くならないという計算量の上限値を表す。 |
| ウ | アルゴリズムの解析では、主要項の部分を除いて比較する。 |
| エ | アルゴリズムを実現した場合の変数領域の大きさを表す。 |
答え イ
【解説】
処理時間や計算時間を比較するときに使用するオーダ記法は、アルゴリズムの最悪値の処理時間や計算時間を意味し、これ以上の時間は掛からないという意味で使います。
ソート(整列)アルゴリズムでオーダ記法がよく使用されますが、この時の値は最も整列に時間のかかる場合を意味しています。
【キーワード】
・オーダ
- オーダ(計算量)
コンピュータの処理時間を考えた場合、最も正確に測定する方法は実際にプログラムを作って実機で処理時間を計測する方法であるが、プログラムの設計段階で2つのアルゴリズムの計算時間を比較する場合には、プログラムを作って比べることは難しいため、各アルゴリズムの計算量を調べて、計算量で比較を行います。
一般にコンピュータの処理で時間がかかるのは、比較演算であるので計算量を考えるときは、そのアルゴリズムの比較演算の回数を用います。
計算量を表す記号はオーダ(程度)を意味するO ( )を使用します。
もっと、「オーダ」について調べてみよう。
戻る
一覧へ
次へ