質問: 2n+1 の実行時間となるのでビッグオーで表すとO(n)ということでよいでしょうか? (2) ``` fnc(n){ if n < 10: return 0; return fnc(n - 3) + 1; } ``` (2)に関してはビッグオーの求め方自体がわかりません。再帰処理がある場合のビッグオーはどのようにして求めたら良いのでしょうか?
回答: オーダーは計算量を「概算で」を求めるものなのでそんな厳密に考えなくてよいです。 (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回のほうが実処理時間が余計に必要であったとしても、それは係数に相当するのでオーダー表記には含めません。