Q&A
学校の課題か何かでしょうか？であれば、まずは担当教官に質問してください。
また、完成しているアルゴリズムが表現されているコードを質問に書きましょう。
「nが変数宣言されていない」、「 } が足りない」、「無限ループする」などコンパイルすらできない問題が多すぎます。
C
1int t = 1; 2void a(void) { 3for(int i=0;i<n;i++) { 4 printf("hello\n"); 5 t++; 6} 7 if(t <4) a(); 8}
上記の場合、再帰を2回呼ぶので計算量はO(n^3)だと思うのですが、どのくらいになるのでしょうか。
申し訳ございません。訂正致しました。
実際にwalk through(頭と手で実行をシミュレート)してみましょう。
n=1の時、printfは何回実行されますか?
n=2の時、printfは何回実行されますか?
n=4の時、printfは何回実行されますか?
n=8の時、printfは何回実行されますか?
nが2倍になるとprintfの実行回数は何倍になりますか?
私にはO(n^3)には見えません。
回答5件
0
n がどこにもないのでコンパイル・エラー。
... n > 4 だったら止まらないんじゃないコレ?
[修正後あらためまして]
n を増やしつつ、a()が何度呼ばれるか調べてみた。
C
1#include <stdio.h> 2 3int t = 1; 4int n = 5; 5int count; 6 7void a(void) { 8 ++count; 9 for(int i=0;i<n;i++) { 10 t++; 11 if(t <4) a(); 12 } 13} 14 15int main() { 16 for (n = 1; n < 10; ++n ) {; 17 t = 1; 18 count = 0; 19 a(); 20 printf( "n= %d\t count= %d\n", n, count); 21 } 22} 23 24/* 実行結果 25n= 1 count= 3 26n= 2 count= 6 27n= 3 count= 9 28n= 4 count= 12 29n= 5 count= 15 30n= 6 count= 18 31n= 7 count= 21 32n= 8 count= 24 33n= 9 count= 27 34*/
ふむ、呼ばれる回数が処理時間と比例するだろうから、計算時間量は O(n) みたいね。
投稿2019/04/18 12:03
編集2019/04/20 05:55
総合スコア16614
n=4でもtが4回インクリメントされてifに入るので、無限ループに突入ですね。
わーい！！
再起の闇だ！！
すみません訂正致しました。
nは外部変数で適当に宣言されているものでかんがえていただきたいです。
申し訳ないです。確認したところforループのブロックの範囲を間違えていました。
If文の前で終わるとO(n^3)では無いでしょうか
あなたがそう判断するなら(そしてそれが十分合理的なら)そうなのでしょう。
で、n^3なんておっきくなります? やってみた?
0
コードは参考にならないので置いといて、読んでみてわからないなら動かしてみればわかるんじゃないですか？
ループ内にカウンタを入れて n を変化させて呼び出した時、計算回数が n に無関係なら O(1) で n に比例するなら O(n) で n^2 に比例するなら O(n^2)
実際にはきっちり比例しなくてもだいたいどのグラフに近いかで判断します。
投稿2019/04/19 04:41
総合スコア28660
質問者さんの過去質問を全て見たわけではないのですが、計算量を示す上で、O記法を充分にご存じでは無いのかな、とは少し思いました。
過去質問のリストを見てすぐ閉じました。これは答えなくていい質問だったみたいです。
そうでしたか。残念です。
0
n >= 4 では a() が一度しか実行されず n 回ループするだけなので、 O(n) ですね。
投稿2019/04/21 13:58
総合スコア6753
0
本題ではないですが、他の人の回答を見て思ったので
大前提ですが、O(n)⊂O(n ^ 2)⊂O(n ^ 3) ですよ。
つまり、O(n)に属すならば、O(n ^ 2）にもO(n ^ 3)にも属すわけです。質問者は以下のように質問しています。
O(n^3)だと思うのですが、どのくらいになるのでしょうか。
O(n)に属するならばこれに対する回答はYesです。理由はどうあれ。
まあそれ以前にプログラム自体なにかおかしいので、多分全体像がみえないと答え出ないでしょうが・・・
投稿2019/04/20 15:53
総合スコア4830
0
質問者さんのコードが意味不明なので、再起の基本を教えます。
下記のコードで試してみて下さい。
デバックしてないのでエラー出たらごめんなさい。
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 03:11
編集2019/04/19 06:08総合スコア3307
stdioさん： (低評価を入れたのは私ではありませんが）C言語ですから、引数で指定している参照の「&」は使えませんよ。
> 再起処理は基本的には要素の数だけ回ります。
と言いますか、再帰と言えども脱出条件は本来、自分で書くものだと思います。質問者さんの元のコードの意味するところが分かりませんのでそこは省きますが、
#include <stdio.h>
void a(const int n) {
if (n <= 0) {
return;
}
printf("n=%d\n", n);
a(n - 1);
}
int main() {
a(5);
return 0;
}
/*
n=5
n=4
n=3
n=2
n=1
*/
のように。
うむ、C++と勘違いしてましたわ。
> 再帰と言えども脱出条件は本来、自分で書くものだと思います。
え、私のコードはしっかりと脱出しますよ。その辺はfor文の仕様です。わざわざif文書かなくてもこの場合はしっかりと通りますよ。
確かに質問者さんの元のコードを元に少し手を加えた感じですけど...
あと、再起中にprintfするとか正気か？
> 私のコードはしっかりと脱出しますよ。
なるほど、確認しました。確かにその通りですね。別の部分に気を取られて不適切な指摘をしてしまいした。大変失礼しました。お詫びします。
> あと、再起中にprintfするとか正気か？
この点はサンプルである限り、即、NGとは言い切れないように思いますが、printfがリエントラントを保障していないかぎり、特に実務や第三者へのサンプルとして使うべきではないとのご指摘であれば、同意します。
まぁ、サンプルだったらいいか。実務で使われると流石に怒るしかなくなくけど...
特に、私の処理の場合はprintf入れたら大変な事になりますので...
「基本的には要素の数だけ回ります」という説明のコードが要素数以上に回ってるので脱出に失敗しているように見えます。
再帰中に printf すること自体には「正気か？」というほどの問題はないと思います。printf をあちこちに散らばらせると保守性が落ちるので、安易に真似るとそれを招きかねないということなら理解できますが、この場合は単なるデバッグプリントにしか見えません。
再帰というのは特殊なループと言えますが、これがダメならループ中で printf を使えなくなります。
（かき回してすみません）自己レスですが、
> リエントラントを保障していないかぎり (更に誤字： s/保障/保証/)
このコードの場合はマルチスレッドでもシグナルハンドラーでもなく、printf実行中に再入することは無いので、リエントラントな関数か否かは関係ありませんでした。単に、極力、スタックを消費しないようにする為。重ねて失礼しました。
> 要素数以上に回ってるので脱出に失敗しているように見えます。
いやそれなら、「再起処理」の意味ねぇよ。
>これがダメならループ中で printf を使えなくなります。
その場合mainでaの関数の値変更すると、ほぼ無限ループのように回り続けるので、printfを書くと処理が終わらんのですわ。
「要素の数だけ」が意味不明なので捕捉があればいいのではないかと思います。
うむ確かに...
少し変更しておきますわ。
printf は重いので再帰に限らず大きなループだと終わらなくなりますね。しかし、再帰は必ずしも大きなループになるとは限りません。dodox86 さんのコードはすぐ終わるので無関係ですし、一般的にあまり深い再帰だとスタックオーバーフローを起こすので、再帰だけの問題ではなく、再帰の中でループを使う、いわゆる多重ループの問題だと思います。これは stdio さんのコードの問題です。
「再帰で printf を使うのは正気を疑うくらい悪い」の意味が処理時間の問題なのであれば、適当ではないと思います。
うむ、私のこのコードは問題だらけだぞ。なんせしっかりと勉強している人でも迷う時あるからね。
printfは私のコードで行うと狂気じみた事になるから、避けたかっただけです。誤解を招くような発言を謝罪しましょう。
あなたの回答
tips
プレビュー
