アルゴリズムの処理時間や問題の計算時間を比較するときに使用するオーダ記法の説明として、適切なものはどれか。
ア | アルゴリズムが解に到達するまでの計算量の下限値を表す。 |
イ | アルゴリズムがこれより遅くならないという計算量の上限値を表す。 |
ウ | アルゴリズムの解析では、主要項の部分を除いて比較する。 |
エ | アルゴリズムを実現した場合の変数領域の大きさを表す。 |
答え イ
【解説】
処理時間や計算時間を比較するときに使用するオーダ記法は、アルゴリズムの最悪値の処理時間や計算時間を意味し、これ以上の時間は掛からないという意味で使います。
ソート(整列)アルゴリズムでオーダ記法がよく使用されますが、この時の値は最も整列に時間のかかる場合を意味しています。
【キーワード】
・オーダ