応用情報技術者試験 H24秋季 午前 問6 アルゴリズムの処理時間や問題の計算時間を比較するときに使用するオーダ記…

Question

応用情報技術者試験 H24秋季 午前 問6

アルゴリズムの処理時間や問題の計算時間を比較するときに使用するオーダ記法の説明として、適切なものはどれか。ㅤ
ㅤアㅤアルゴリズムが解に到達するまでの計算量の下限値を表す。
ㅤイㅤアルゴリズムがこれより遅くならないという計算量の上限値を表す。
ㅤウㅤアルゴリズムの解析では、主要項の部分を除いて比較する。
ㅤエㅤアルゴリズムを実現した場合の変数領域の大きさを表す。

正答：イ

ウやエでない理由は解るのですが、イの正しさがしっくり来ません。

あるプログラムからオーダを算出する際には最長経路を取る、ということなのでしょうか？
例えば以下のJavaメソッドがあったとします。

int calc(int n) {
ㅤif (Math.random() < 0.5) {
ㅤㅤreturn 0;
ㅤ} else {
ㅤㅤwhile (n > 0) {
ㅤㅤㅤn--;
ㅤㅤ}
ㅤㅤreturn 1;
ㅤ}
}

この場合にはO(1)ではなくO(n)ということ？

Answer 1

ビッグオー記法の定義は、そもそも計算量の上限を与えるということです。
この問題は、この定義を知っているかどうかだけです。下限については別途ビッグオメガ記法があります。計算量の評価として使われているところを見たことはありませんが・・・。

なお、条件分岐があるアルゴリズムにおいては、条件分岐の枝の双方で個別に計算量を見積もり、その最悪値(より大きい方)を全体の計算量とすることになります。つまり今回の場合で言えば、ifの条件にあった場合は、O(1)、そうでない場合は、O(n)です。したがって、全体はO(n)です。
O(1)+O(n)=O(n)
などと表現する場合もあります。