アルゴリズムクイックリファレンス第二版 要約ノート １章・２章・３章
主に自分用に。この本は俺にとっては上司。身近にいそうな上司だ。
結構難しめの本なんで、実際に買うのは立ち読みで4章ぐらいまで読んでみてからの方が良いのではないか、とは思う。
1章 『アルゴリズムで考える』
- 「アルゴリズム設計の第1ステップは、解きたい問題の理解である。」
- 「既存のアルゴリズムの種類に簡単に分類できそうにない」問題の紹介。「自明な探索方式もなさそうだ。」
- 非効率的な素朴解の提示。「本書の多くのアルゴリズムは、既存のコードに対してさらに効率的なコードを求め努力した結果である。」
- 実例による、貪欲法・分割統治法・並列法・近似法・一般化、の紹介。「しかし、正確な解を計算しなくても、誤差が正確に把握できて、かつ迅速に計算できる近似解で十分なこともあるだろう。」「より一般的な問題を解くことができると、元の問題を解くのにその解をすぐ変換できるということがよくある。」
- 「効率的なアルゴリズムは、まったく明らかでないことがよくある。データセット、（並列性を使えるかどうかなどの）プロセス環境、目標などに依存して、まったく異なるアルゴリズムが最良となることもしばしばある。この簡単な紹介は、アルゴリズムの表面をなでただけにすぎない。本書で取り揃えたさまざまなアルゴリズムだけでなく、こういった異なるアプローチについてももっと学ぼうという気になってほしい。紹介するすべてのアルゴリズムについては、実装して、適切なドキュメントと説明を加えてある。これらは、アルゴリズムをどのように使うか、さらには自分でどう実装するかまでを理解する助けになるだろう。」
2章 『アルゴリズムの数学』
- アルゴリズムの計算量の記述において、定数分を掛けただけの性能コストの違いは無視する。問題インスタンスのサイズによる成長率によって記述する。
- アルゴリズムの性能は、最悪時・平均時・最良時で提示されることが多い。
- この本における性能の分類として
- 定数 O（1）
- 対数 O（log n）
- 下位線形 d<1について O（n^d）
- 線形 O(n)
- 線形対数 O(n log n)
- 二乗 O(n^2)
- 指数 O(2^n)
※ちなみにここでの「log」とは底が2である「log[2]」のことで、「log n」は「log[2]n」を意味している。要するに2を何回掛けたらnになるかという話で、「log 8」は3だし、「log 64」は6だ。この「log」という指標がアルゴリズムにおいては重要になる。「8 log 8」は8*3=24。
3章 『アルゴリズムの構成要素』
- 基本的にはこの本における説明のテンプレートを紹介。
- 浮動小数点について。個人的には、こちらの「浮動小数点数」の方が分かりやすかった。（ https://www.cc.kyoto-su.ac.jp/~yamada/programming/float.html )
- 「一般的な浮動小数点の誤差の記述には、絶対誤差の本来の値に対する割合を計算した相対誤差が使われる。」つまり、「誤差/全体の数値」。
- 浮動小数点同士の比較では、基本的には「==」にならないので注意。普通の解決法としては、許容する誤差を決めて、一方から一方を引いて絶対値がそこに収まっているかを確認する。ただしこの単純な尺度でも、x≒yかつy≒zであっても、x≒zが真にならない可能性がある。「さらに追加すれば、この解法では、値の符号（0、正、負）を用いて決定する共線問題は解くことができない。」
- 一般的なアプローチの紹介。貪欲法・分割統治法・動的計画法。「貪欲戦略は、アルゴリズムが入力を処理するにつれて、解かれる部分問題が徐々に狭くなると特徴づけることもできる。」
