T_NAKAの阿房ブログ

アクセスカウンタ

zoom RSS プログラムの複雑さについて(2)

<<   作成日時 : 2015/12/31 00:01   >>

なるほど(納得、参考になった、ヘー) ブログ気持玉 1 / トラックバック 0 / コメント 0

今回は exp2 を例に考えてみましょう。


画像
この図の真ん中、exp2(a,b) について手数を考えていきます。
これは再帰的プログラムですね。\(b==1\) という条件が成立しなければ、
 
の右辺を実行することになります。
では手数(の増加)を考えてみます。ここで、\(t(b)\) を、サイズ \(b\) の問題を解決するための手順の数とします。
つまり、
\[
t(b)=チェック(b==1)+減算(bから1引く)+乗算(aをかける)+t(b-1)=3+t(b-1)
\] 
となるでしょう。ところで、\(t(b-1)=3+t(b-2)\) なので、
 
    
となり、これも手数の増加量は入力引数に線形で、漸近的表記 (asymptotic notation) を使うと
 
と表現されることになります。

今日はこの辺で。。


テーマ

関連テーマ 一覧


月別リンク

ブログ気持玉

クリックして気持ちを伝えよう!
ログインしてクリックすれば、自分のブログへのリンクが付きます。
→ログインへ
気持玉数 : 1
なるほど(納得、参考になった、ヘー)

トラックバック(0件)

タイトル (本文) ブログ名/日時

トラックバック用URL help


自分のブログにトラックバック記事作成(会員用) help

タイトル
本 文

コメント(0件)

内 容 ニックネーム/日時

コメントする help

ニックネーム
本 文
プログラムの複雑さについて(2) T_NAKAの阿房ブログ/BIGLOBEウェブリブログ
文字サイズ:       閉じる