T_NAKAの阿房ブログ

アクセスカウンタ

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

<<   作成日時 : 2016/01/05 00:01   >>

ブログ気持玉 0 / トラックバック 0 / コメント 0

exp1 と exp2 は同じ線形でしたが、exp3 はどうなるか?を考えます。

画像
今回は再右端のexp3(a,b)について手数を考えていきます。
これは exp 2(a,b) と似ていますが、\(b\) が偶数の場合、
  
と変形が出来て、手数が半分になる可能性があります。この場合
\[
t(b)=チェック(b==1)+割り算(b割る2)+乗算(2をかける)+チェック(bが偶数) +乗算(aの2乗)
\]
\[
+割り算+t(b/2)=6+t(b/2)
\] 
\(b\) が奇数の場合、
\[
t(b)=チェック(b==1)+割り算(b割る2)+乗算(2をかける)+チェック(bが偶数) +乗算(aをかける)
\]
\[
+引き算(b-1)+t(b-1)=6+t(b-1)
\]
となります。
ここで、\(t(b-1)\) は偶数なので、一般的には
 
となるでしょう。以降続けると
 
であり、最終的に終わるのは
 
であり、このプログラムの計算量を漸近的表記 (asymptotic notation) を使うと
 
と表現されることになります。

今日はこの辺で。。

テーマ

関連テーマ 一覧


月別リンク

ブログ気持玉

クリックして気持ちを伝えよう!
ログインしてクリックすれば、自分のブログへのリンクが付きます。
→ログインへ

トラックバック(0件)

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

トラックバック用URL help


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

タイトル
本 文

コメント(0件)

内 容 ニックネーム/日時

コメントする help

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