第1章

1.1 効率の必要性

大きなデータセット

• Googleの検索に8.5秒も必要、とされているのは注釈欄のコンピューターの速度が数ギガヘルツ(数十億回/秒)なのを$10^9$ 回/秒として、85億件のWebページをすべて見ようとすると(データセットの要素をすべて見るという前提はその前の段落に書いてある)$\frac{8.5\times10^8}{10^9} = 8.5$ 秒かかるということ

• 38250台のサーバーが必要、とされているのは一つのリクエストに8.5秒かかるという前提で複数サーバーで並列処理できた場合、一つのリクエストに1秒でレスポンスするには1/8.5台のサーバーが必要。秒間4500クエリ受け付けているので$4500 \times \frac{1}{8.5} = 38250$ 台のサーバーが必要ということ

1.3 数学的背景

1.3.1 指数と対数

• 自然対数と二進対数との比較 $$\ln k = \frac{\log_2 k}{\log_2 e} = \frac{\log_2 k}{\frac{\log_e e}{log_e 2}} = \log_e 2 \times \log_2 k = \ln 2 \times \log_2 k$$

1.3.2 階乗

• $\ln (n!)$ の近似値はその前で示されているスターリングの近似($n! = \sqrt{2\pi n} (\frac{n}{e})^n e^{\alpha(n)}$ )を使って $$\ln (n!) \newline = \ln (1 \times 2 \times ... \times n) \newline = \ln (\sqrt{2\pi n} (\frac{n}{e})^n e^{\alpha(n)}) \newline = \ln \sqrt{2\pi n} + \ln (\frac{n}{e})^n + \ln e^{\alpha(n)} \newline = \ln (2\pi n)^\frac{1}{2} + \ln n^n + \ln e^{-n} + \ln e^{\alpha(n)} \newline = \frac{1}{2}\ln (2\pi n) + n\ln n - n + \alpha (n)$$

1.3.3 漸近記法

ビッグオー記法は今までなんとなく使っていたが正しい定義は初めて見た。$O(f(n))$ は集合を表していて、nがある程度より大きいときは定数倍しても常に$f(n)$ より小さくなる関数の集合、というような意味合いだった。$f(n)$ はどんな関数でも構わないはずだが、アルゴリズムの世界でよく使われるのが$\alpha$ (定数)、 $\log n$ 、$n^b$ 、$c^n$ などなのだろう。ある関数が$O(f(n))$ に含まれるということは定数倍しても$f(n)$ に満たなく、ある関数とはアルゴリズムの世界では例えば実行時間である。つまり実行時間を表す関数が$O(f(n))$ に含まれるということは、最悪でも$f(n)$ 内には実行完了するし、$f(n)$ に含まれる関数の間での実行時間の差は大きくても定数倍なので丸めて$O(f(n))$ で同じ、といってしまって良いよね、ということである。

1.3.4 ランダム性と確率

• コインをk回投げたときの表が出る回数の期待値を期待値の定義を使って求めている。$\dbinom{k}{i}$ は $${}_k C _i$$ のようである。 二項係数の性質$i\dbinom{k}{i} = k\dbinom{k-1}{i-1}$ も、 $${}_k C_i = k{}_{k-1} C_{i-1}$$ で表される。