プログラムの実行時間

[初心差]

f(n)=f(n-1)+f(n-2), f(1)=1, f(2)=2という関数があり、f(n)を求める以下の２つのプログラムの実行時間を比較しなさい。という問題ですが、プログラムを見ただけで実行時間はどうすれば分るのでしょうか？
以下、その２つのプログラムです。

プログラムＡ
#include <stdio.h>

main(){
int a,b,c,i,N;

scanf("%d",&N);
a=0;
b=1;
for(i=1;i<=N;i++){
c=a+b;
a=b;
b=c;
}
printf("%d",c);
}


プログラムB
#include<stdio.h>

int f(int n){
if(n>=3)
return(f(n-2)+f(n-1));
if(n=2)
return(2);
if(n=1)
return(1);
}
main(){
int N;
scanf("%d",&N);
printf("%d",f(N));
}

よろしくお願いします。

[h2so5]

そもそもプログラムが間違っているんですが、本当にこの通りの問題なんでしょうか。

[みけCAT]

プログラムを見ただけで実行時間を求めるのは相当きついと思います。
Linuxならtimeコマンドで実行時間が測れます。
Windowsなら、例えばこのツールが使えます。
http://www.vector.co.jp/soft/win95/hard ... 64269.html

また、コードはcodeタグで囲んでいただけるとありがたいです。

[初心差]

すみません。プログラムを囲むのを見落としていました。
できればペーパーテストですので、ＰＣなしで解きたいです。

正確にはＮの値が5 10 20 40 41 42 の場合に何秒かかったか、５種類の実行結果があたえられており、そのうちから１つずつ選ぶというもです。

[みけCAT]

プログラムから計算量オーダーを判断すると、計算時間が見積もれます。
プログラムAのオーダーはO(N)です。（実行時間がだいたいNに比例します）
これはそのままです。
プログラムBのオーダーはO(2^N)です。（実行時間がだいたい2^Nに比例します）
これは図を書いてみるとわかりやすいです。

プログラムB

saiki.png (9.48 KiB) 閲覧数: 3666 回

[たいちう]

いい問題だと思うけど、h2so5さんの指摘通りプログラムが間違ってます。
上級者は脳内だけでも、ある程度プログラムの動きをシミュレートできるので、
間違いに気付けますが、机上では初心者には少々難しいでしょう。


実行時間について、「N==42の時に何秒かかる」とかを求めるのは一般的には不可能です。
PCの性能等に依存するのは理解できますよね？


で、本題ですが、アルゴリズムを注意深く観察 or 脳内や紙上で追っていき、
足し算が実行される回数を数えることはできそうですか？
小さいNから、2つのプログラムの足し算の数を比較してみれば、
法則性を見つけることができるはずです。

[初心差]

>>みけCATさん
詳しい説明ありがとうございます。
実行時間がＮに対してどのくらいの割合で比例するかわかれば解けそうです。
ありがとうございます。
>>たいちうさん
足し算の回数を数えればよいんですね。みけＣＡＴさんの画像を参考にすればできそうです。
ありがとうございました。

再確認したところ、プログラムの間違いというのはＢの
　if(n=2)
return(2)
if(n=1)
return(1)
がn==でなく、n=となっているところでしょうか？
すみません。打ち間違えました。

[たいちう]

> 足し算の回数を数えればよいんですね。

この問題に限っては、そうです。
足し算の回数だけで、実際にかかる時間の傾向を「ある程度の範囲で」推測できます。

[初心差]

了解しました。
皆さんありがとうございました。