3

引数 n が負の整数でなく、アルゴリズムの実行時間 = 代入の数 + 数を加算する数とする場合のビッグオー、ビッグシータの求め方について、

(1)

fnc(n){
    a=0 // +1回
    if nが奇数: 
         for i = 1 to n: // +n回
            a += 1;      // +n回
    return a;
}

↑の関数の場合nが奇数なら合計1+n*2 = 2n+1 の実行時間となるのでビッグオーで表すとO(n)ということでよいでしょうか?

(2)

fnc(n){
    if n < 10:
        return 0;
    return fnc(n - 3) + 1;
}

(2)に関してはビッグオーの求め方自体がわかりません。再帰処理がある場合のビッグオーはどのようにして求めたら良いのでしょうか?

6
  • 漸近的挙動には関係ありませんが、コメントの書き方を見るに、for i = 1 → n というループでは 1 から n までではなく 1 から (n-1) までループするのですか?
    – nekketsuuu
    Commented 2017年9月8日 9:45
  • 打ち間違いだと思いますが、引数が x だったり n だったりしています。適宜編集して頂ければ幸いです。
    – nekketsuuu
    Commented 2017年9月8日 9:51
  • (2)のfunfncの打ち間違いかと思います。確認をお願いします。
    – letrec
    Commented 2017年9月8日 11:24
  • @nekketsuuu 誤字修正しました。for文に関しては1からnまでのループです。
    – ynbenson
    Commented 2017年9月8日 12:15
  • @ynbenson それではたとえば i に対する代入は (n-1) 回ではなく n 回起こるのではないでしょうか。
    – nekketsuuu
    Commented 2017年9月8日 12:22

2 件の回答 2

5

基本的には、ランダウの記法の定義通りに考えることになります。リンクした Wikipedia 記事だと「その他の漸近記法」にまとめられています。

ビッグオーは関数を上からおさえる、ビッグオメガは関数を下からおさえる、ビッグシータは両方からおさえる "気持ち" があり、その直感のもと数学的な定義がなされていると考えてください。

(1)

はい。fnc(n) の実行時間は O(n) です。つまり「このアルゴリズムの実行時間の "増え方" は、1次関数の "増え方" より程度が小さい」です。もう少し厳密に言うと「ある大きな定数 k について、このアルゴリズムの実行時間は kn 以下である」ということです。

では、実行時間が O(n) になることを数学的に厳密に証明してみます (必要ない場合は(2)まで読み飛ばしてください)。

(1)の「アルゴリズムの実行時間」を T(n) とおきます。すると

(1)の T(n) を式で書き下した数式

という形に書きくだせます。ここで gg(n) = n という関数とします。このとき上の式を見ると、どんな n についても T(n) ≦ 3 × g(n) が成り立つことが分かります。(ここでいう 3 が、ランダウの記法を使うときの「定数倍」のことです。3 という定数倍を無視すれば、Tg によって上からおさえることができました。)以上より、ビッグオー記法の定義から、T(n) = O(g(n))、つまり、T(n) = O(n) であると証明できました。

なお、同じように、どんな n についても T(n) ≧ 1 なので T(n) = Ω(1) であることも証明できます。また、どんな正の定数 k についても n が2以上の偶数のとき T(n) = 1 ≧ kn ではないので T(n) ≠ Ω(n) です。したがって T(n) = Θ(n) ではありません。

(注: 細かいことを言うと、実際にプログラムを実行する際には if 文の中の奇数判定にも計算時間がかかるはずですが、今回の「実行時間」の定義だと奇数判定の計算時間を0だと思ってもあまり影響が無いためそのようにしました。より厳密には奇数判定のアルゴリズムも記述した上で、その実行時間を T(n) に加えるべきです。)

(2)

再帰関数で表されたアルゴリズムの実行時間は、一般的には漸化式を使って求めることになります。ただし今回の再帰関数の場合、どんな風に関数が呼び出されていくかを想像すると、再帰呼出しは大雑把に n 回程度しかおきないことが分かるため、計算時間は O(n) であると直感的に言うことはできます。

しかしそれだと厳密ではないので、(1)と同様に数学的な証明を書きます。(2)の「アルゴリズムの実行時間」を T(n) とおきます。今回の定義では「実行時間」に大小比較や関数呼び出しは含まれていないことに注意してください。さて、アルゴリズムを見て考えると、T(n) について以下の漸化式が成り立つことが分かります。

(2) の T(n) に関する漸化式

今回の場合、この漸化式は簡単で、そのまま解けてしまいます。漸化式を解いて T(n) の正体を明らかにしてから (1) と同様にオーダーを確かめるという方法でも証明はできるのですが、今回は大体 O(n) だろうという予想が立っているので、数学的帰納法を使った別の方法で証明します。

n が非負整数のとき T(n) ≦ n であることを数学的帰納法を使って証明します。まず 0 ≦ n < 10 のとき、T(n) = 0 ≦ n なので成り立ちます。次に n ≧ 10 のときを考えます。0 ≦ m < n ならば T(m) ≦ m であると仮定します。定義より T(n) = T(n - 3) + 2 です。帰納法の仮定から T(n - 3) ≦ n - 3 が成り立ちます。よって T(n) ≦ (n - 3) + 2 = n - 1 ≦ n となります。以上より、大きな n について T(n) ≦ n であることが証明できました。したがってビッグオー記法の定義より、T(n) = O(n) であることも証明できました。

ついでに下から抑えられるかどうかについても考えてみます。実は同じように上の漸化式を使いつつ数学的帰納法を用いることによって「n が 10 以上の整数のとき T(n) ≧ n/6 であること」が証明できます。よって定義より T(n) = Ω(n) です。したがって T(n)O(n) でも Ω(n) でもあることが証明できたので、定義より T(n) = Θ(n) であることも証明できました。

ちなみに T(n) の漸化式を真面目に解くと

(2) の T(n) の漸化式を解いて書き下した式

となります。(実際に n = 10, 11, 12, 13, ... を代入すると上の漸化式で得られる値と同じになることを確認してください。) この式を見ると、n が充分大きい所では T(n) がどれも一次式なので、T(n) = Θ(n) であることがすぐに分かります。( (1)と同じように証明できます。) 漸化式が簡単に解けそうなら、このように T(n) の正体を明らかにしてやると直接オーダーが計算できます。

補足

簡単なアルゴリズムの実行時間オーダーは、慣れてくるとループのネストの数や再帰の仕方などを見て感覚的に分かるようにはなります。しかし、厳密にそのことを示せと言われると、やはり数学的な世界に立ち入る他ありません。

今回のご質問のような内容は「アルゴリズムとデータ構造」などという名前の教科書によく書かれています。たとえば「アルゴリズムとデータ構造 計算量 再帰関数」でググると大学の講義資料が出てくるので、参考にしてみてください。また、Qiita にも「[初心者向け] プログラムの計算量を求める方法」という記事がありました。

より立ち入った話をすると、この分野は「計算量の漸近的挙動の解析」として知られています。計算量理論の教科書ではまっさきに書かれていることの1つなので、適当な教科書を1つ読んで勉強なさるのも良いと思います。個人的にはウェブ上にある河村彰星先生の「計算量演習.pdf」がオススメです。今回の話題だと、PDF 末尾にある第A章の演習問題が面白いと思います。書籍だと『計算理論の基礎 3.複雑さの理論』などがあります。

5
  • (1)の証明に関しては理解できたのですが、(2)の場合 nが10以上の場合T(n-3)+1になりませんか?数学的帰納法を用いた証明でT(n - 3) ≦ n - 3 が成り立った場合なぜ` T(n) ≦ (n - 3) + 2 = n - 1 ≦ n`が成り立つのか教えてほしいです
    – ynbenson
    Commented 2017年9月8日 16:05
  • (2) の漸化式ですが、n - 3fnc(n - 3) + 1 とで2回加減算が入るため +2 されます。
    – nekketsuuu
    Commented 2017年9月8日 16:16
  • 帰納法の部分について: n ≧ 10 のとき、漸化式より T(n) = T(n - 3) + 2 なので、T(n - 3) ≦ n - 3 とあわせて T(n) = T(n - 3) + 2 ≦ (n - 3) + 2 が成り立つことが分かります。
    – nekketsuuu
    Commented 2017年9月8日 16:17
  • わかりやすい説明ありがとうございます! 最後に(2)でθの数学的帰納法により「n が 10 以上の整数のとき T(n) ≧ n/5 であること」を証明する際の手順を教えていただけないでしょうか。まず n=10 のとき、実行時間は22以上なので成立。そのあと 10≦m<n ならば T(m) ≧ m を仮定し、定義が T(n) = T(n - 3) + 2 のため T(n - 3) ≧ n - 3 とあわせて T(n) = T(n - 3) + 2 ≧ n - 1 が成立…これで証明完了なのでしょうか?
    – ynbenson
    Commented 2017年9月8日 21:04
  • すいませんその部分間違えていました。n/5 じゃなくて n/6 ですね。 / まず n=10, 11, 12 のときどれも T(n) = 2 となるので T(n) ≧ n/6 です。次に 13 ≦ n のときを考えます。10 ≦ m < n ならば T(m) ≧ m/6 を仮定し、計算すると T(n) ≦ n/6 が導かれます。 / 帰納法の仮定は示したい命題と同じ形をしていなければいけないことと、仮定を使うときにはちゃんと m として使える範囲にいるかどうかを確認しなければいけないことに注意してください。
    – nekketsuuu
    Commented 2017年9月9日 2:02
0

オーダーは計算量を「概算で」を求めるものなのでそんな厳密に考えなくてよいです。

(1) Yes
ループが1段しかなくて n 回なのでオーダーは O(n)
オーダー表記では係数は考えません。なのでループ内の計算が1個でも2個でも O(n)

(2) fun(x-3) ということは再帰する回数は n に比例するのでオーダーは O(n)
係数は考えないので fun(x-3) でも fun(x-1) でも O(n)
ループ1回より関数呼び出し1回のほうが実処理時間が余計に必要であったとしても、それは係数に相当するのでオーダー表記には含めません。

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。