初めての店舗開業を成功させよう>>

再帰呼び出しを用いた関数の計算量を求める方法がわからないので質問させていただきます.
xのn乗を再帰呼び出しを用いて求める関数に関して,計算量を求める問題なのですが,どのような方針で求めればよいのでしょうか?

int exponent(int x, int n)
{
  if(n == 0){
    return 1;
  }else{
    return x * exponent(x, n-1);
  }
}

exponentがn回呼ばれるからO(n)というのは間違いでしょうか?

A 回答 (1件)

計算量は n のみに依存し x には依存しません. なので, exponent(x, n) の計算量を T(n) とおきます.


T(0) = O(1), T(n) = T(n-1) + O(1)
と書けます. この漸化式を解けば T(n) = O(n).
「exponent が n回呼ばれるから O(n)」というのは省略しすぎです. exponent の中の (再帰呼び出し以外の) 計算量が O(n) だったら, そのようには言えませんよね.
「exponent の中で再帰呼び出し以外の計算量が O(1) で, exponent そのものは都合 n回呼び出されるから O(n)」とまで書いてあればいいかもしれない. 読む人によってよいとしたりだめとしたりするかもしれません.
    • good
    • 0
この回答へのお礼

回答ありがとうございます.

なるほど,漸化式を用いて求めればいいんですね.
詳しい説明,ご忠告ありがとうございました.

お礼日時:2009/07/04 13:16

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Q【C言語】再帰が時間がかかる理由について

再帰のプログラムがなぜ時間がかかるのかを詳しく調べています。

アセンブリレベルで見ると、
callに時間がかかるのか?それともpop命令?それとも退避?
結局、よく分からないまま、
Google検索して調べています。(まだよくわかってません。)

再帰呼び出しのデメリットは、
スタック領域を大量に消費する、関数呼び出しのオーバーヘッドであること。

この事実はわかりました。
しかしながら、
オーバーヘッドとは具体的に何なのか
これを調べています。

どなたか、良いサイト・書籍を知らないでしょうか。
教えてください。

Aベストアンサー

2つの要因があると思います。

--------
1つ目は次の例のように,再帰的定義の中に自分自身が1つだけ登場する場合です。

「1からnの総和」
F(n)=n+F(n-1) …(n>1 であること)
F(1)=1

F(5)
=5+F(4)
=5+(4+F(3))
=5+4+(3+F(2))
=5+4+3+(2+F(1))
=5+4+3+2+1

この場合,上記に示したように,結果的に行われる計算自体は次のループと変わらず,5+4+3+2+1 を行っています。

s = 0;
for (i = n; i >= 1; i--) {
s = s + i;
}

しかし,5,4,3,2,1のそれぞれを求めるために再帰では毎回関数呼び出しを用いています。
回答No.1・No.2の指摘どおり「関数呼び出しを用いること自体がオーバヘッドである」ということです。

--------
2つ目は次の例のように,再帰的定義の中に自分自身が複数登場する場合です。

「フィボナッチ数」
F(n)=F(n-1)+F(n-2) …(n≧2 であること)
F(1)=1
F(0)=0

F(5)
=F(4)+F(3)
=(F(3)+F(2))+(F(2)+F(1))
={(F(2)+F(1))+(F(1)+F(0))}+{(F(1)+F(0))+1}
=[{(F(1)+F(0))+1}+(1+0)]+{(1+0)+1}
=[{(1+0)+1}+(1+0)]+{(1+0)+1}
=5

フィボナッチ数は,0, 1, 1, 2, 3, 5, 8, 13, 21, 44, ……のように列挙できる,前2者の和です。

この再帰の場合,前述の「関数呼び出し自体がオーバヘッドである」ことはもちろんなのですが,加えて「関数呼び出しの回数が増えていること」が新たなオーバヘッドとなります。

具体的には,次の★で示したF(2)を求める箇所(ちなみに,F(2)=F(1)+F(0)=1+0=1です)は3つ登場しますが,

F(5)
=F(4)+F(3)
=(F(3)+F(2)★)+(F(2)★+F(1))
={(F(2)★+F(1))+(F(1)+F(0))}+{(F(1)+F(0))+1}

ある★箇所で求めたF(2)の値を,他の★箇所で流用することは再帰では行われません。式が2つの項に分かれ,4つの項に分かれ,と分割されていきますが,ある一つの項で値を求める際,すでに他の項でその値が算出済であるかどうか知りませんし,自分が求めた値をそれを必要とするであろう他の項に教えようともしません。

再帰的定義の中に自分自身が複数登場する場合は,関数呼び出しの回数がネズミ算的に増えていきます。

2つの要因があると思います。

--------
1つ目は次の例のように,再帰的定義の中に自分自身が1つだけ登場する場合です。

「1からnの総和」
F(n)=n+F(n-1) …(n>1 であること)
F(1)=1

F(5)
=5+F(4)
=5+(4+F(3))
=5+4+(3+F(2))
=5+4+3+(2+F(1))
=5+4+3+2+1

この場合,上記に示したように,結果的に行われる計算自体は次のループと変わらず,5+4+3+2+1 を行っています。

s = 0;
for (i = n; i >= 1; i--) {
s = s + i;
}

しかし,5,4,3,2,1のそれぞれを求めるために再帰で...続きを読む


人気Q&Aランキング

おすすめ情報