37811


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

(1)

[code]

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

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

(2)

[code]

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

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


CC BY-SA 3.0
2017-09-08T02:45:07.267
37796
2017-09-09T02:45:20.353
2017-09-08T13:21:38.403
19110
18535
question
アルゴリズム 計算量
ビッグオー、ビックシータの計算方法 (関数に再起がある場合、if文がある場合等)


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

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

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


CC BY-SA 3.0
2017-09-08T04:35:15.553
37798
2017-09-08T04:35:15.553
8589
37796
answer


基本的には、[ランダウの記法](https://ja.wikipedia.org/wiki/%E3%83%A9%E3%83%B3%E3%83%80%E3%82%A6%E3%81%AE%E8%A8%98%E5%8F%B7)の定義通りに考えることになります。リンクした
Wikipedia
記事だと[「その他の漸近記法」](https://ja.wikipedia.org/wiki/%E3%83%A9%E3%83%B3%E3%83%80%E3%82%A6%E3%81%AE%E8%A8%98%E5%8F%B7#.E3.81.9D.E3.81.AE.E4.BB.96.E3.81.AE.E6.BC.B8.E8.BF.91.E8.A8.98.E6.B3.95)にまとめられています。

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

### (1)

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

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

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

> [![\(1\)の T\(n\)
> を式で書き下した数式](https://i.stack.imgur.com/uAFzc.png)](https://i.stack.imgur.com/uAFzc.png)

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

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

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

> [![\(2\) の T\(n\)
> に関する漸化式](https://i.stack.imgur.com/1sf6Q.png)](https://i.stack.imgur.com/1sf6Q.png)

今回の場合、この漸化式は簡単で、そのまま解けてしまいます。漸化式を解いて `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\)
> の漸化式を解いて書き下した式](https://i.stack.imgur.com/TdbVe.png)](https://i.stack.imgur.com/TdbVe.png)

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

### 補足

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

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

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


CC BY-SA 3.0
2017-09-08T11:02:38.130
37811
2017-09-09T02:45:20.353
2017-09-09T02:45:20.353
19110
19110
37796
answer