質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.82%

再帰関数を用いたプログラムの計算量(オーダー)の求め方がわかりません。

受付中

回答 5

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 2,133

apeirogon0813

score 72

int t = 1;
void a(void) {
for(int i=0;i<n;i++) {
 printf("hello\n");
 t++;
}
 if(t <4) a();
}


上記の場合、再帰を2回呼ぶので計算量はO(n^3)だと思うのですが、どのくらいになるのでしょうか。

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • mather

    2019/04/18 23:09

    学校の課題か何かでしょうか?であれば、まずは担当教官に質問してください。
    また、完成しているアルゴリズムが表現されているコードを質問に書きましょう。
    「nが変数宣言されていない」、「 } が足りない」、「無限ループする」などコンパイルすらできない問題が多すぎます。

    キャンセル

  • 退会済みユーザー

    2019/04/19 09:11

    複数のユーザーから「やってほしいことだけを記載した丸投げの質問」という意見がありました
    「質問を編集する」ボタンから編集を行い、調査したこと・試したことを記入していただくと、回答が得られやすくなります。

  • apeirogon0813

    2019/04/20 13:52

    申し訳ございません。訂正致しました。

    キャンセル

  • sage

    2019/04/29 17:29

    実際にwalk through(頭と手で実行をシミュレート)してみましょう。
    n=1の時、printfは何回実行されますか?
    n=2の時、printfは何回実行されますか?
    n=4の時、printfは何回実行されますか?
    n=8の時、printfは何回実行されますか?

    nが2倍になるとprintfの実行回数は何倍になりますか?
    私にはO(n^3)には見えません。

    キャンセル

回答 5

+3

n がどこにもないのでコンパイル・エラー。

... n > 4 だったら止まらないんじゃないコレ?

[修正後あらためまして]

n を増やしつつ、a()が何度呼ばれるか調べてみた。

#include <stdio.h>

int t = 1;
int n = 5;
int count;

void a(void) {
  ++count;
  for(int i=0;i<n;i++) {
    t++;
    if(t <4) a();
  }
}

int main() {
  for (n = 1; n < 10; ++n ) {;
    t = 1;
    count = 0;
    a();
    printf( "n= %d\t count= %d\n", n, count);
  }
}

/* 実行結果
n= 1     count= 3
n= 2     count= 6
n= 3     count= 9
n= 4     count= 12
n= 5     count= 15
n= 6     count= 18
n= 7     count= 21
n= 8     count= 24
n= 9     count= 27
*/

ふむ、呼ばれる回数が処理時間と比例するだろうから、計算時間量は O(n) みたいね。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/04/20 13:53 編集

    すみません訂正致しました。
    nは外部変数で適当に宣言されているものでかんがえていただきたいです。

    キャンセル

  • 2019/04/20 14:47

    申し訳ないです。確認したところforループのブロックの範囲を間違えていました。
    If文の前で終わるとO(n^3)では無いでしょうか

    キャンセル

  • 2019/04/20 14:49 編集

    あなたがそう判断するなら(そしてそれが十分合理的なら)そうなのでしょう。
    で、n^3なんておっきくなります? やってみた?

    キャンセル

+1

コードは参考にならないので置いといて、読んでみてわからないなら動かしてみればわかるんじゃないですか?
ループ内にカウンタを入れて n を変化させて呼び出した時、計算回数が n に無関係なら O(1) で n に比例するなら O(n) で n^2 に比例するなら O(n^2)
実際にはきっちり比例しなくてもだいたいどのグラフに近いかで判断します。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/04/19 14:33

    質問者さんの過去質問を全て見たわけではないのですが、計算量を示す上で、O記法を充分にご存じでは無いのかな、とは少し思いました。

    キャンセル

  • 2019/04/19 14:38

    過去質問のリストを見てすぐ閉じました。これは答えなくていい質問だったみたいです。

    キャンセル

  • 2019/04/19 14:47

    そうでしたか。残念です。

    キャンセル

0

n >= 4 では a() が一度しか実行されず n 回ループするだけなので、 O(n) ですね。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

-1

本題ではないですが、他の人の回答を見て思ったので

大前提ですが、O(n)⊂O(n ^ 2)⊂O(n ^ 3) ですよ。

つまり、O(n)に属すならば、O(n ^ 2)にもO(n ^ 3)にも属すわけです。質問者は以下のように質問しています。

O(n^3)だと思うのですが、どのくらいになるのでしょうか。

O(n)に属するならばこれに対する回答はYesです。理由はどうあれ。

まあそれ以前にプログラム自体なにかおかしいので、多分全体像がみえないと答え出ないでしょうが・・

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

-5

質問者さんのコードが意味不明なので、再起の基本を教えます。
下記のコードで試してみて下さい。

デバックしてないのでエラー出たらごめんなさい。

int count = 1;
void a(int n) {
  for(int i = 0; i < n; i++) {
    count++;
    a(n - 1);
  }
}

int main(void){
  a(10);//ここの値変更すると面白いよ。
  printf("%d\n",count);
}

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/04/19 15:04

    うむ確かに...
    少し変更しておきますわ。

    キャンセル

  • 2019/04/19 15:11

    printf は重いので再帰に限らず大きなループだと終わらなくなりますね。しかし、再帰は必ずしも大きなループになるとは限りません。dodox86 さんのコードはすぐ終わるので無関係ですし、一般的にあまり深い再帰だとスタックオーバーフローを起こすので、再帰だけの問題ではなく、再帰の中でループを使う、いわゆる多重ループの問題だと思います。これは stdio さんのコードの問題です。

    「再帰で printf を使うのは正気を疑うくらい悪い」の意味が処理時間の問題なのであれば、適当ではないと思います。

    キャンセル

  • 2019/04/19 15:26

    うむ、私のこのコードは問題だらけだぞ。なんせしっかりと勉強している人でも迷う時あるからね。

    printfは私のコードで行うと狂気じみた事になるから、避けたかっただけです。誤解を招くような発言を謝罪しましょう。

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.82%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る