アルゴリズム読み物を読みたくて、いろんなところでオススメされている数学ガールの乱択アルゴリズムを読んだ。なかなか興味深かった。
この本で興味深かったことは以下の二点。
- 具体例 -> 規則性 -> 一般化で考える
- アルゴリズムの実行ステップ数の数学的な解析
具体例 -> 規則性 -> 一般化で考える
この本で、問題を考えるときは、具体例を考える -> 規則性を見つけ出す -> 一般化する、という3ステップで考える、ということが書かれていた。
例えば「n枚のカードを一列に並べる方法は、全部で何通りあるか」という問題を考えてみる。この時、n枚のカードのまま一般的に考えようとしてよく分からなくなってしまうという失敗をしてしまうことが多い。そうではなくて、
- まずは1枚ならどうか、2枚ならどうか、3枚ならどうかと具体例を考える
- 具体例を見つめて、規則性を探し、イメージを付ける
- 最後にnの場合でどうなるか、一般化して考える
と、3ステップで考えると良い。
このことは非常に当たり前のことなんだけど、なぜかいつも慌てて一般的に考えて理解不能に陥ることが多い。そのようにならないように、具体例 -> 規則性 -> 一般化という言葉を頭に留めておきたい。
アルゴリズムの実行ステップ数の数学的な解析
この本で特に興味深かったのは、アルゴリズムの実行ステップ数を解析する部分。普通のアルゴリズムの書籍だと、ループの回数の解析でリニアサーチはO(n)、バイナリサーチはO(log n)、バブルソートはO(n^2)、クイックソートはO(n log n)のように説明されていることが多い。しかし、この本では擬似コードの1行1行の実行ステップ数を考え、それを数学的に計算することでオーダーを求めるという、別視点での解析をしている。解析方法にもいろいろあることが知れたのが良かった。
以下のアルゴリズムを数学的に解析しているので、興味があれば読んでみると良さそう。
まとめ
アルゴリズム読み物として、数学ガール/乱択アルゴリズムを読んだ。読み物はいくつも読んだし、少し飽きてきた部分もあるので、とりあえずアルゴリズム読み物系は置いておき、本格的にアルゴリズムの勉強をしようかなと思う。
今は文字列関係のアルゴリズムに一番興味があり、また最近Elasticsearchを触ることもあったので、全文検索エンジンを実装することでアルゴリズムの学習を進めていきたい。あとdiffのアルゴリズムも興味があるので、そのあたりも機会があったらやっていきたい。あとはきちんとアルゴリズムクイックリファレンスを読んでおきたい。
diffの動作原理を知る～どのようにして差分を導き出すのか：一般記事｜gihyo.jp … 技術評論社
読書ノート
- アルゴリズムの持っている特徴は、入力・出力・明確性・実効性・有限性 41
- 入力があると、その出力が存在する
- 手順が明確である
- 手順を実際に行うことができる
- 実行時間が有限である
- 40ページから、リニアサーチのアルゴリズムの解析が始まる。ここでいつもだったら特に検討せずにO(n)とか話すことが多いが、ちゃんと実行ステップを計算していくのが良い。
- 問題を考えるときは、具体例を考える -> 規則性を見つけ出す -> 一般化する、というフローで考えていく 73
- オーダーの記法
- Θ記法: ちょうどf(n)のオーダー
- Ω記法: 少なくともf(n)のオーダー
- O記法 : たかだかf(n)のオーダー
- オーダーを表す時、logに底を書かない理由 203
- バイナリサーチの実行ステップ数を数学的に解析する方法が210から始まる 210
- バブルソートの実行ステップ数の解析 225
- 比較ソートの最大比較回数が少なくともn * lognのオーダーになるかを、比較木を利用して証明する 229
- クイックソートの実行ステップ数を数学的に解析する 390
