数列と近似と計算量

今日は何のために役に立つのかわからない高校数学No. 1の数列について。

結論を述べる。ソフトウェアエンジニア、特に高負荷環境のゲームエンジニアやバックエンドエンジニアにとって有用な教養となる。

数列

数の列

数が並んでいるものを数列（numerical sequence）という。

$$
1,5,5,6,3,4,2, \cdots
$$

適当に並べたが数は自然数でも実数でも複素数でもなんでも良い。適当に並べるとあまり意味がないので、この数列に何らかの法則性がある場合を考える。

等差数列

「1年目の預金が5万円、2年目から毎年3万円預金し続けた場合、7年目の預金額は？」。書き出してみよう。

$$
5,8,11,14,17,20,23\cdots
$$

答えは$${23}$$。では、書き出さないで求める方法は？おそらく脳内でこういう計算をしたと思う。

$$
5 + 3 * (7 - 1) = 23
$$

これを抽象化する。$${n}$$番目の値を$${a_n}$$と定義すると

$$
a_n = 5 + 3  (n - 1) = 3  n + 2
$$

こういう数列を等差数列という。別の見方をしてみる。新しい数はその前の数によって決まっているからこうも書ける。

$$
a_n = a_{n-1} + 3
$$

ただし、$${a_1 = 5}$$である。こういう形の数列を漸化式という（「漸化」の由来がよくわからなかったので誰が知っていたら教えてほしい。英語だとrecurrence relation=再帰的関係、あるいはdifference equation=差分方程式という、こちらの方が直感的だと思う）。

等比数列

「厚さ0.5mmの薄い板がある、6回折り曲げたら厚さはどれくらいになる？」。書き出してみよう。

$$
0.5,1,2,4,8,16,32,\cdots
$$

答えは$${32}$$mm、さっきと同じように計算式を考えると

$$
a_n = 0.5  * 2^{n-1}
$$

漸化式の形で書くと

$$
a_n = 2  a_{n-1}
$$

ただし、$${a_1 = 0.5}$$である。

フィボナッチ数

次のような数列をフィボナッチ数という。

$$
1,1,2,3,5,8,13,21,\cdots
$$

漸化式の形で書くと

$$
a_n = a_{n-1} + a_{n-2}
$$

面白い性質を持つがここではあまり触れない。ここで重要なこととして、数列を表現するのに数列を使って良いということが分かれば良い。

数列の和

次のような数列を考える

$$
\frac{1}{2},\frac{1}{4},\frac{1}{8},\frac{1}{16},\frac{1}{32},\frac{1}{64},\frac{1}{128},\cdots
$$

明らかに

$$
a_n = \frac{1}{2} a_{n-1}
$$

ただし、$${a_1 = 1/2}$$。これの$${n = 7}$$までの総和（sum）は？

$$
a_1 + a_2 + a_3 + a_4 + a_5 + a_6 + a_7 = \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \frac{1}{16} + \frac{1}{32} + \frac{1}{64} + \frac{1}{128}
$$

これをまとめて書く記法がある。

$$
\sum_{k = 1}^{n} a_n = a_1 + a_2 + a_3 + a_4 + a_5 + a_6 + a_7
$$

・・・。この記号、わたしが高校ではじめて見た時、全く意味がわからなかった（だから数列はずっと苦手だった。読み方の決まりはないが「シグマエーエヌ」等と呼ぶ）。$${\sum}$$（シグマ）は$${k}$$の関数とも言えるので、適当に$${k}$$を組み入れても良い

$$
\sum_{k = 1}^{n}  \frac{1}{k!} a_n^k
$$

等（この式には特に意味はない。読み方としては「シグマ、k階乗分の1、エーエヌのk乗」）。また、フィボナッチ数は明らかに数列の和の形で書ける。

$$
a_n = \sum_{k = 1,2} a_{n-k}
$$

極限

無限

さっきの数列を思い出す。

$$
\frac{1}{2},\frac{1}{4},\frac{1}{8},\frac{1}{16},\frac{1}{32},\frac{1}{64},\frac{1}{128},\cdots
$$

これの無限（infinite）番目はなんだろうか。直感的にはわかる、$${0}$$だ。これをこう書く。

$$
\lim_{n \rightarrow \infty} a_n = 0
$$

これを極限（limit）が$${0}$$に収束（convergence）するという。横着すると$${a_\infty}$$と書くことがある。ここでは極限の定義には触れないが、

$$
a_\infty = \frac{1}{2} a_\infty
$$

が成立する$${a_\infty}$$は$${0}$$しかない。

無限の総和と近似

これの総和を求めたい

$$
\frac{1}{2},\frac{1}{4},\frac{1}{8},\frac{1}{16},\frac{1}{32},\frac{1}{64},\frac{1}{128},\cdots,0
$$

これは直感的にはわかる、$${1}$$だ。というより$${1}$$を半分ずつにしていくと上になる。上の数列の場合は厳密な極限値を計算できるが、一般にはそうではない。ただ、少しずつ値が小さくなっていっていることがわかるなら、無限まで計算しなくても最初の方の値だけで大雑把には計算できる。例えば、7番目まで計算すれば

$$
 \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \frac{1}{16} + \frac{1}{32} + \frac{1}{64} + \frac{1}{128} = 0.992 \approx 1
$$

真の極限値との誤差は1%以下になる。こういう形でざっくり計算することを近似（approximation）という。さらにこれの特別な場合がテイラー展開を利用した線形近似になる。

これについては長くなるので端折る。

並べ替えと計算量

ソートの問題

コンピュータサイエンスの世界へ、数を小さい順に並べ替えるということをやってみよう。これをソート（sort）という。方法は色々あるがここでは比較的わかりやすいマージソート（merge sort）を扱う。

8 4 3 7 6 5 2 1

これを並べ替えるのに次を行なう

• 2つに分ける：「8 4 3 7」「6 5 2 1」

• さらに分ける：「8 4 」「3 7」「6 5」「 2 1」

• さらに分ける：「8」「 4 」「3」「 7」「6」「5」「 2」「1」

• 2つを並べながら統合する：「4 8」「3 7」「5 6」「1 2」

• さらに並べながら統合する：「3 4 7 8」「1 2 5 6」

• さらに並べながら統合する：「1 2 3 4 5 6 7 8」

要点は2つある。1つ目は、問題を小分けにして各々を独立して解決するということ。2つ目は、すでに並んでいる2つの数列を合わせるのは簡単であるということ。

次に、これの計算量（computational complexity）を出してみる。$${n}$$個の数をソートする計算量を$${T_n}$$とする。さっきの方法だと、分割した先の計算量と統合する計算量でこれを表現できるから

$$
T_n = 2  T_{n / 2} + c  n
$$

1個を並べる計算量は$${T_1 }$$、既に並んでいる数列を合わせる計算量は$${c  n}$$とする（固定倍、実際に行なうとわかるが小さい方から順に選んでいくだけなのでこれ以上のコストはない）。わかりやすく$${n = 2^k}$$と仮定して、$${T_n = T_{2^k} = T'_{k}}$$とすると

$$
T'_{k} = 2  T'_{k-1} + c  2^k
$$

展開する

$$
T'_{k} = 2 (2  T'_{k-2} + c 2^{k-1}) + c 2^k = 2^2 T'_{k-2} + 2  c 2^k
$$

さらに

$$
T'_{k} = 2^2 (2  T'_{k-3} + c 2^{k-2}) + 2  c 2^k = 2^3 T'_{k-3} + 3  c 2^k
$$

つまり

$$
T'_{k} = 2^l T'_{k-l} + l c 2^k 
$$

さらに$${l = k - 1}$$とすると

$$
T'_{k} = 2^{k-1} T'_{1} + (k - 1)  c 2^k 
$$

このまま計算を進めても良いが少し楽をしよう。

ランダウの記号

今、求めた式には2つの項があるが、$${n}$$が十分大きい時、どちらの方が大きいだろうか。式を少し変形してみる。

$$
T'_{k} = \left(  T'_{1} + 2  c  (k - 1) \right) 2^{k - 1}
$$

例えば、$${k=20}$$なら$${n=1048576}$$である。こういう場合、明らかに2項目の方が大きい（$${T'_{1}}$$や$${c}$$は、単位によるが$${10}$$より小さいと思って良い。$${T'_{1}}$$は「1個の数を並べる時間」だから「そのデータ1個へのアクセス時間」と等価である）。

つまり、1項目は無視して近似できる。

$$
T'_{k} \approx c  (k - 1)  2^k
$$

$${n = 2^k}$$と置いたことを思い出すと

$$
T_n = T'_{k} \approx c \left( \frac{\log n}{\log 2 } - 1 \right) n
$$

ところで、また2項あるが2項目の影響は1項目よりも小さい。$${\log n}$$の影響が強いからだ。2項目を消して近似する。

$$
T_n \approx \frac{c}{\log 2}  n \log n
$$

ところで係数の$${\frac{c}{\log 2} }$$には何の意味があるだろうか。これはかなり具体的な1回の操作に係る時間を表す値だ。データはどこにあるだろう。CPUのレジスタにあれば1ナノ秒、メインメモリにあれば1マイクロ秒、HDDにあれば1ミリ秒、物理的なトランプを使って遊んでいれば1秒、そのとき手を怪我していれば10秒必要になる。

ここで考えたいのは、この並べ方が良いか悪いかだ。物理的な条件を考えたいわけではない。つまりこの係数に意味はない。よって適当な係数に比例することだけが分かれば良い。

$$
T_n \propto n \log n
$$

あらためて考えると最も影響力の大きい項しか見ていないし、その係数も見ていない。そこで、ランダウの記号を使ってこれをこう表現する。

$$
O(n \log n)
$$

読み方は「オーダーエヌログエヌ」（単に「エヌログエヌ」という方が多いと思う。普通はこれで通じる）、これはデータ量の増加に対して、その処理時間がどれくらい大きくなるかを表す。代表的なものは

• $${O(1)}$$：固定

• $${O(\log n)}$$：対数

• $${O(n)}$$：線形

• $${O(n \log n)}$$：準線形

• $${O(n^2)}$$：2乗

• $${O(2^n)}$$：指数

もし、データが10億レコード（$${n = 10^9}$$）あって、その計算のオーダーが$${{O(n^2)}}$$だったら、その計算量は$${10^{18}}$$だ。桁が大きすぎてもうよくわからない。これがDBにインデックスを貼る理由であり、規模の大きいサービスのバックエンドエンジニアにパフォーマンスチューニングを求める理由となる。

おわりに

力尽きたので予告

• アルゴリズムとデータ構造

• MySQLとB-Tree