「プログラマの数学」を読みました

で、勉強したことを書いて行こうと思います。

網羅的に書くことはできないので、ひとまず、「第７章指数的な爆発」について書いてあったことを自分なりにまとめながら書いて見ます。

まず、表題の「指数的な爆発」とは、指数関数が爆発的な増加をする、という性質を表したものです。

爆発的な増加、とは、f(x)がxの関数であるとき、xが少し増えるだけで、f(x)が爆発的に増える、ということです。

少しとか、爆発的に、とか、すでに厳密でない定義が頻出していますが、少し、というのはf(x) = xのようなもの、で、爆発的に増えると噂の指数関数はf(x) = 2^x(2のx乗)のようなものです。

x = 1の時の両者の値と、xが10の時の両者の値は圧倒的に差があります。

(グラフだとわかりやすいんですが、他の参考サイトを見つけることができませんでした。。)

指数的な爆発をする状況というのは、プログラマ的には避けるべき状況です。

計算量という指標でも、指数オーダのアルゴリズムというのは、時間がかかるアルゴリズムである、という前提があるため、特別な理由がなければ、使用は推奨されません。

しかし、指数的な爆発を計算が収束する速度として生かす方法もあります。

例えばバイナリサーチです。

1ステップ進むごとに対象項目を1/2にすることができます。

1024個あるものから目的のものを見つけるのに、順番に見ると1024回判定を繰り返すのに対し、1024 => 512 => 256 => 128 => 64 => 32 => 16 => 8 => 4 => 2 => 1と、わずか10ステップで絞り込むことができます。

少し視点をずらして、爆発的であるがために、非常に観察しづらい指数的な増加を観察する方法を考えます。

そこで持ち込まれるのが、対数という概念です。

例えば、ある数字Aは10のB乗、という表現をした場合に、Bという数字を大きさとして評価する考え方です。

これですと、例えば、10の5乗は、5と表現されます。

100000と連ねるよりもずっと小さな世界で、指数の変化を観察できます。便宜上Bという数値を表すのにB = log10(A)という書き方をします。

爆発的で人間の目には捉えることができない指数的爆発も一度対数の世界に持ち込むことで、理解がしやすくなります。

対数の世界で観察、計算したことを、元の指数の世界に戻すことで、新たな知見を得ることもできるようになります。

以上の通り、この章では、指数的爆発とは、から始まり、指数的爆発の利用、指数的爆発の観察方法を説明されていました。

ということで今回はおしまいです。

次回はあるかな～。

余談。

学生時代に初めて対数を習った時、なんじゃこりゃ？急に出てきたこの概念何？と思いましたが、この本では具体的に使用例や、便利なところを真っ先に表示してくれます。これは本当にすごく大事なことだと思いました。

(学生時代の私が単に先生の話を聞いてなかっただけ、という可能性はある気がしますが。。)