• ベストアンサー

再帰呼び出しの計算量

再帰呼び出しを用いた関数の計算量を求める方法がわからないので質問させていただきます． xのn乗を再帰呼び出しを用いて求める関数に関して，計算量を求める問題なのですが，どのような方針で求めればよいのでしょうか？ int exponent(int x, int n) { 　　if(n == 0){ 　　　　return 1; 　　}else{ 　　　　return x * exponent(x, n-1); 　　} } exponentがn回呼ばれるからO(n)というのは間違いでしょうか？

noname#95388
noname#95388

質問者が選んだベストアンサー

  • ベストアンサー
  • Tacosan
  • ベストアンサー率23% (3656/15482)
回答No.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)」とまで書いてあればいいかもしれない. 読む人によってよいとしたりだめとしたりするかもしれません.

noname#95388
質問者

お礼

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

  1. カテゴリ
  2. [技術者向] コンピューター
  3. プログラミング・開発
  4. C・C++・C#

関連するQ&A

  • 再帰を用いた場合の計算量

    nの階乗を再帰呼び出しを用いて計算する以下のプログラムの計算量はいくらになるのでしょうか？ 調べてみてもどこにも記述されていなくて困っています． int factorial(int n) { 　　if(n > 0) 　　　　return (n * factorial(n - 1)); 　　else 　　　　return (1); } また，できれば求め方も教えていただけると嬉しいです．

  • nCrの計算

    nCrの計算のプログラムを nCr=n!/(r!(n-r)!) を用いて再帰的関数を使って書いたのですが、もし nCr=n(n-1)(n-2)・・・(n-r+1)/r! であることを用いて、nからmまでの掛算を実現する2引数の関数を定義して、再帰的関数呼び出しを用いたnCrのプログラムを作成するとしたらどうなるでしょうか。 関数x!の定義は、関数の宣言をlong factorial(int x)として、 if (x==0) return(1); else return(x*factorial(x-1)); となることは分かるのですが、 2引数の関数m(m+1)・・・nはどう作れば良いのか全くわからないので、プログラムが書けない状態です。アドバイスお願いします。

  • c言語の再帰で(関数呼び出し)+1がわからない

    再帰がどのように処理されているのか理解するために、再帰の時に +1 してみたところ 0! = 1 1! = 2 2! = 5 3! = 16 4! = 65 5! = 326 6! = 1957 7! = 13700 8! = 109601 9! = 986410 10! = 9864101 となりました。 普通の階乗の値を求めた最後に +1され、それが戻されると思ったのですが違いました。 これはどういう処理がされているのでしょうか？ #include <stdio.h> int kaijo(int); int main() { int i; for (i = 0; i < 11; i++) printf("%d! = %d\n", i, kaijo(i)); return 0; } int kaijo(int n) { if (n == 0) return 1; else return n * kaijo(n - 1) + 1; }

  • 再帰・組み合わせ

    新しく再帰という概念を習い始めたのですが、組み合わせを求めるやり方がわかりません 組み合わせの公式通り（nCk　→　n!/k!(n-k)!）、例えば4C2なら答えは6通りになるのはわかるのですが、 public static int combinations(int n, int k){ if(k==n){ return 1; }else if(k=1){ return n; }else if(0<k && k<n){ combinations(n-1, k-1) + combinations(n-1, k) ←これで出来るらしいのです } } combinations(n-1, k-1)は意味がわかるのですが、combinations(n-1, k)これが組み合わせの公式にどうあてはまっているのかがわからず、 そして何故足してるのかがよくわかりません。どなたかお解かりになればお願いします

    • ベストアンサー
    • Java
  • 再帰呼び出し

    アッカーマン関数の値を出力するプログラム #include void main(void); int ack(int,int); void main(void) { int x,y,i; printf(" data(x) = "); scanf("%d",&x); printf(" data(y) = "); scanf("%d",&y); i = ack(x,y); printf("Ackerman = %d\n",i); } int ack(int a,int b) { int k; if (a == 0) k = b+1; else if (b == 0) k = ack(a-1,1); else k = ack(a-1,ack(a,b-1)); return (k); } この関数を呼び出した回数も出力するようにしたいのですが、どうしたらいいのでしょうか？

  • 再帰関数について

    非負の整数nに対して次のように定義された 関数F(n),G(n)がある。F(5)の値はいくらか。 関数 F(n)：if n=<1 then return1 else return n×G(n-1) G(n)：if n=0 then return0 else return n+F(n-1) (1)50　(2)65　(3)100　(4)120 正解 (2)65 以下解説 F(5)：5×G(5-1)=5×(G(4)) 　　　=5×(4+F(4-1))=5×(4+(F(3))) 　　　=5×(4+(3×G(3-1)))=5×(4+(+3×G(2)))) 　　　=5×(4+(3×(2+F(2-1))))=5×(4+(+3×(2+F(1))))) 　　　=5×(4+(3×(2+(1)))) 　　　=65 再帰関数についての知識が皆無なので 教えて頂きたいのですが、なぜ=後の5×は残るのでしょうか。 そもそも再帰関数とは、どんなことを言っているのでしょうか。 具体例を挙げて頂くか、分かり易いURLを教えて頂けると幸いです。 お手数ですが、上記について1つ1つ丁寧に解説して頂きたいです。 大変ご迷惑な質問かと思いますが、分かる方おられましたら、 お手数ですが、ご教授お願いします。 以上、よろしくお願い致します。

  • 再帰呼び出し

    C++のクラスで n!=n(n-1)(n-2)...1 n!を求めるprogramを作らなくてはならないのですが 再帰を使わずに、関数factorial(n)を使わないといけません。 ちんぷんかんぷんです。 for（counterとcounter--を使った）物しか思いうかびません。 関数factorial(n)を使うというのはnに戻るつまり再帰というふうには ならないのですか？ 関数と再帰の意味を漠然としかわかっていないのですが。 よろしくお願いします。

  • VC++ 再帰呼び出しについて

    VC++6.0にてプログラミングを行っているものですが、 関数の再帰呼び出しについて質問です。 再帰呼び出しの際にスタックに積まれる変数というのは、 再帰呼び出しをする関数に渡す引数のことですか？ スタックオーバーフローを起こさないために、 staticなポインタにHeap領域上の 変数を割り当てるとよい。 と分かったのですが、 この意味は、例えば static int *a = new int; ということなのですか？

  • 再帰呼び出しについて

    これらの関数をうまく結びつけるにはどうしたらよいのでしょうか？ Tree *henkan(void) { int suu; int yusen; suu=next(); yusen=check_yusen(suu); if(yusen==-1) return; if(yusen==1) check_1(suu); else if(yusen==2) check_2(suu); else if(yusen==3) check_3(suu); } void check_1(char suu) { Tree *n1; suu=toint(suu); suu=check_suu(suu); n1=make_node(suu,0,0); push(n1); henkan(); } void check_2(char suu) { Tree *n1; Tree *n2; henkan(); n2=pop(); n1=pop(); result=make_node(suu,n1,n2); push(result); } void check_3(char suu) { Tree *n1; Tree *n2; int num; n1=pop(); num=next(); num=toint(num); num=check_suu(num); n2=make_node(num,0,0); result=make_node(suu,n1,n2); push(result); henkan(); } int check_suu(int suu) { int check; int num; num=next(); check=check_yusen(num); if(check==1) { num=toint(num); suu=10*suu+num; suu=check_suu(suu); return suu; } else if(check==-1) return suu; else { sikip--; return suu; } }

  • 関数の再帰処理

    1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657... という数列（フィボナ数列）を再帰処理でだしたいのですが・・・・・ include <stdio.h> int function( int ); int main( void ){ int n; do { printf( "0 以上の整数値を入力して下さい→ " ); scanf( "%d", &n ); }while ( n < 0 ); printf( "計算結果： %d\n", function( n ) ); getchar(); getchar(); return 0; } int function( int n ){ //フィボナの処理（function）の再帰呼び出しによる } function内に再帰処理を用いてprintf( "計算結果： %d\n", function( n ) );で画面出力したいのですが・・・・・・。

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する