Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest：Introduction to Algorithms

概要

アルゴリズムの概論である。 私がもっているのは初版である。 なお、2016年11月現在、原著は第3版となっていて、著者に Clifford Stein が加わっている。

感想

鬼のように厚い本である。初版の邦訳版では3分冊になったほどだ。なお、第３版の邦訳は原書と同じく一冊ものとなった。 これだけの量を理解できないといけない合衆国の学生は大変である。 この本のいいところは、いわゆる標準的なアルゴリズム （ソーティング、文字列照合）のほか、 計算幾何学や数値計算などのアルゴリズムも一緒に扱っていることである。

分類定理

p.62 で 分類定理の説明がある。 アルゴリズムで、分類定理とは次の形の定理をいう。英語では master theorem というので、マスター定理というのが誤解を与えないのでいいのかもしれない。 以下、訳してみる。

`a gt 1 と b gt 1` を定数とし、`f(n)` を関数とする。`T(n)` を非負整数上、次の再帰式で定義されるものとする。
`T(n) = a T(n//b) + f(n)`
ここで、`n//b` を `|__ n//b__|` と `|~n//b~|` の平均と解釈する。このとき、`T(n)` は漸近的につぎのように評価される。

1. もしある正の定数 `epsilon` に対して `f(n) = O(n^(log_b a - epsilon))` ならば、 `T(n) = Theta(n^(log_b a))`
2. もし `f(n) = Theta(n^(log_b a))` ならば、 `T(n) = Theta(n^(log_b a) lg n)` である。
3. もしある正の定数 `epsilon` に対して `f(n) = O(n^(log_b a + epsilon))` ならば、 そしてある定数 `c lt 1 ` に対して `a f(n//b) lt cf(n)` であり、`n` が十分に大きい場合は、 `T(n) = Theta(f(n))` である。

対数

`lg n = log_2 n` であり、二進対数と名付けられている。

数式の記述

数式は ASCIIMathML を用いている。

まりんきょ学問所 ＞ コンピュータの部屋 ＞ コンピュータの本 ＞ アルゴリズム ＞ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest：Introduction to Algorithms