T_NAKAの阿房ブログ

アクセスカウンタ

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

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

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

簡単な例で、もう少し複雑さについて考えます。

次は掛け算の簡単なルーチンで基本は足し算の繰り返しです。
画像

内部のループは \(O(m)\) で、外側のループは \(O(n)\) なので、全体では \(O(mn)\) ということになります。
\(m=n\) なら \(O(n^{2})\) ということです。

次にPython のおさらい(18)再帰的プログラムの例ハノイの塔を考えることにします。
画像

再帰的プログラムなので、コードは凄く簡単ですね。しかし、私は良く理解できませんでした。
\(n\) 枚のディスクをAの柱からBの柱に移すことを考えると、\(n-1\) 枚のディスクを正しい順番でCの柱に移しておかなくてはいけません。
そうでないと、一番下にある一番大きな\(n\) 枚目のディスクをAからBに移すことが出来ません。
さらに、\(n\) 枚目を移した後、その上に\(n-1\) 枚のディスクを正しい順番で重ねなければいけません。
ここで、手数を考えます。
 
となりますが、少し解説が必要でしょう。右辺の最初の \(1\) はこれが最後かどうか?を調べる手数であり、\(t(1)\) は\(n\) 枚目のディスクを移す手数です。
その他に、\(n-1\) 枚のディスクを正しい順番でCの柱に移し、その\(n-1\) 枚のディスクを\(n\) 枚目の上にを正しい順番で重ねなければならないので、\(t(n-1)\) の2倍を加えるということになります。もう少しまとめると、
    
となるでしょう。これは漸化式になっているので、
 
    
    
    
となります。
つまり
 
ということで指数アルゴリズムということになります。

今日はこの辺で。。

テーマ

関連テーマ 一覧


月別リンク

ブログ気持玉

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

トラックバック(0件)

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

トラックバック用URL help


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

タイトル
本 文

コメント(0件)

内 容 ニックネーム/日時

コメントする help

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