T_NAKAの阿房ブログ

アクセスカウンタ

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

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

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

Python のおさらい(18)再帰的プログラムの例で述べたプログラム例は、その複雑さについて考察するものでした。コンピュータサイエンスとプログラミング入門(Part1)の講義に沿って勉強し直しましょう。

まず、べき乗を求める簡単な関数を三つ並べてみました。
exp1(3,4)、exp2(3,4)、exp3(3,4) は全て、34 = 81 を吐き出します。

画像
まず、exp1(a,b) について手数を考えていきます。このプログラムの手数を主要な部分は WHILEループ なので、そこを考えてみます。

画像


この図で分かるように手数は \(3b+2\) です。グラフにすると、

画像


つまり、手数の増加量は入力引数に線形ですね。漸近的表記 (asymptotic notation) を使うと
 
と表現されることになります。

ここでは一番簡単な例を考えてみました。
別の例は後記事で考えることにします。

今日はこの辺で。。

テーマ

関連テーマ 一覧


月別リンク

ブログ気持玉

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

トラックバック(0件)

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

トラックバック用URL help


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

タイトル
本 文

コメント(0件)

内 容 ニックネーム/日時

コメントする help

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