C言語のオーダーについて
情報   C 削除 
注目度
1
閲覧数
2191
解決済
暇なときに
このエントリーをはてなブックマークに追加
hello
(9pt)
int fanc(int b, int n) {
   if ( n == 0 )
        return 1;
   else
        return b * func(b, n-1);
}



この関数の計算コストをオーダで答えなさい。その理由も述べること。

という問題なのですが、



乗数をNとすると、
計算量は、N+1となり、よって
\bf{O}(N)となる。


じゃだめでしょうか??



正解か不正解か。もしよろしければ正答を教えていただけると助かります。
2010-06-30 16:17:36
wosugi
(12pt)
fanc()=func()と解釈します。(質問時は誤字脱字等はよく見直したほうが良いと思います)
これは  b^n を求める関数でしょうか??。(なぜn==1のときにreturn b;じゃないのか・・・)

「計算量はN+1となり・・・」では、
計算 量が何の計算量を指すのか不明確ですし、、
またそれがなぜN+1になるのかを説明してないため、
答 えとしては認められないと思います。


一般に、再帰関数のオーダーを考えるときは、以下の2点を考えます。
・その関数一回あたりのオーダーは?
・その関数は何回呼ばれるか?
これらの積がオーダーとなります。

今回のケースでは、func()はn回呼ばれ、
func()内にループは存在せず O(1) ですね。
よって、その積 O(n) が答えとなります。

2拍手 |
2010-06-30 17:19:52
hello
(9pt)
すみません。誤字のチェックをせずに投稿してしまいました。

正しくは、関数名funcです。


なるほど。そこのところの説明が不明確でした。
というよりは、説明の仕方の根本を知らず恥ずかしいところです。


助かりました!ありがとうございます。
2010-06-30 17:25:30
一言投稿 (Q&Aに関して、思ったことなどをつぶやいてみよう!)
一言投稿はまだありません

そのままでしばらくお待ちください


しばらくたっても変わらない場合はキャンセルしてください

キャンセル

以下の内容で回答を投稿します

よろしいですか?

回答内容

回答の投稿が完了しました

こちらからご確認ください