Grokking Algorithms

目次

第1章　あれもこれもアルゴリズム

第2章　並べたり差し込んだり選んだり：ソート

第3章　同じ手順で何度でも：再帰

第4章　ちっちゃくしてから考えよう：クイックソート

第5章　関連付ければ話も早い：ハッシュテーブル

第6章　グラフを作れば見えてくる：幅優先探索

第7章　本からピアノへ物々交換大作戦：ダイクストラ法

第8章　問題は続くよどこまでも：貪欲法

第9章　ドロボーは計画的に：動的計画法

第10章　分類したら予測して：ｋ近傍法

第11章　この先にはなにがあるの？

第12章　答え合わせ

第1章　あれもこれもアルゴリズム

二分探索

とは

昇順または降順にソートされたデータ構造から、目的の値を探し出すアルゴリズムの一つ

データ構造がソートされている場合、探索にかかる時間が短くなる

二分探索は、以下の手順で行われる

1. 探索対象のデータ構造をソートする。

2. 探索対象のデータ構造の中央にある要素を取り出す。

3. 中央の要素と目的の値を比較する。

4. 目的の値が中央の要素より大きい場合、探索範囲を中央より右側に絞り込む。

5. 目的の値が中央の要素より小さい場合、探索範囲を中央より左側に絞り込む。

6. 目的の値が中央の要素と一致した場合、探索を終了する。

7. 探索範囲がなくなるまで、2から6の手順を繰り返す。

この手順により、データ構造を一度だけ走査することで、目的の値を探し出すことができる

ビッグオー記法

とは

ビッグオー記法は、アルゴリズムの**漸近的時間計算量**を表す際に用いられる記法の一つで、**アルゴリズムの実行時間が入力サイズに対してどのように増加するか**を表現します。

具体的には、アルゴリズムの実行時間が入力サイズ n に対して O(f(n)) で表される場合、入力サイズが増加するにつれて実行時間が f(n) の割合で増加することを意味します。

例えば、二分探索の実行時間を O(log n) で表すことができます。これは、入力サイズが倍になるごとに実行時間が1増えるわけではなく、入力サイズが倍になるごとに実行時間が1回分減少することを意味します。このように、ビッグオー記法を用いることで、アルゴリズムの実行時間がどのように増加するかをわかりやすく表現することができます。

ビッグオーは、最悪の場合の時間計算量を表現する

ビッグオーは、そのアルゴリズムが最短で実行できる時間計算量を表現する訳ではありません。最悪の場合の時間計算量を表現する

第2章　並べたり差し込んだり選んだり：ソート

配列とリンクリスト

概要

配列とリンクリストは、データを格納するためのデータ構造である

配列はメモリ上の連続的な領域にデータを格納し、インデックスにより直接アクセス可能

リンクリストはメモリ上の非連続的な領域にデータを格納し、要素間の接続はリンクにより管理

※これらのデータ構造を適切に選択することは、アルゴリズムのパフォーマンスを最適化する上で非常に重要となる

配列

読み取り：計算量はO(1)、インデックスによる直接アクセスが可能

挿入：計算量はO(n)、挿入位置以降の全要素を移動させる必要がある

削除：計算量はO(n)、削除位置以降の全要素を移動させる必要がある

リンクリスト

読み取り：計算量はO(n)、ヘッドから指定位置までリンクを辿る必要がある

挿入：計算量はO(1)（ただし挿入位置を探す計算量はO(n)）、リンクの更新だけで要素を追加可能

削除：計算量はO(1)（ただし削除位置を探す計算量はO(n)）、リンクの更新だけで要素を削除可能

table:比較表

配列 リンクリスト

読み取り Ｏ(1) Ｏ(n)

挿入 Ｏ(n) Ｏ(1)

削除 Ｏ(n) Ｏ(1)

第3章　同じ手順で何度でも：再帰

まとめ

再帰とは関数が自身を呼び出すこと

全ての再帰は基本ケースと再帰ケースで構成される

再帰とは何か

「再帰」はアルゴリズムとデータ構造の領域で一般的に使用されるコンセプトで、ある関数が自分自身を呼び出す方法を指す。

再帰の問題解決手順

再帰による問題解決は、下記二つの要素によって構成されている

1. 基本ケース

関数が自己呼び出しをせずに直接解を返すケース。問題がそのまま解決可能な最も単純な形式を取る

2. 再帰ケース

関数が自身を再帰的に呼び出すケース。問題をより単純な形（サブ問題）に分割し、その解を組み合わせて元の問題を解決する形式を取る

再帰とスタック

下記のサンプルコードにおいては、

ケース2は、再帰処理が終わらないので、スタックに変数がプッシュされたまま永久にポップされないことになる

code:sample.py

def callback(num):

if num > 10 && num < 100

print('ok')

return;

else

print(num)

callback(num + 1)

# ケース1

num_one = 8

callback(num)

# 8

# 9

# 10

# "ok"

# "ok"

# "ok"

# "ok"

# "ok"

# ケース2

num_two = 100

callback(num)

# 100

# 101

# 102

# 103

# ...

# 1000000

# ....

# 無限ループ

再帰のメリット・デメリット

メリット

一部の問題に関しては、再帰を使用することでコードをシンプルに保てるようになる。特に、木構造や分割統治法によって表現できる問題に対しては有効となりうる。

ループを使うよりも状態を保持する必要がなくなるケースが多いため、ループを使用するよりも、直感的に書ける・読める。

数学的な定義に従ったアルゴリズムを直接実装することが可能になる

デメリット

大量の再帰呼び出しはオーバーヘッドをもたらし、パフォーマンスに影響を及ぼす場合がある

再帰は一見直感的であるとは言え、理解やデバッグが難しいと感じる人もいる

使い所

ループを使用した場合よりもコードをシンプルにすることができる問題に有効

代替案

1. ループ

再帰の代わりにループを使用すると、スタックオーバーフローのリスクを避けることができる。これは特に大きな入力に対するイテレーションが必要な場合に有効。

再帰が同じ計算を何度も繰り返す場合（これによってパフォーマンスが低下する場合がある）、計算結果をキャッシュして再利用することでパフォーマンスを改善できる

この最適化では、再帰呼び出しが関数の最後の操作となるようにコードを書くことで、コンパイラやインタプリタがそれをループに変換することが可能になる。これによりスタックオーバーフローのリスクを軽減できる（※ただし、すべての言語や環境が末尾再帰最適化をサポートしているわけではないことに注意）

第4章　ちっちゃくしてから考えよう：クイックソート

分割統治

分割統治とは、そのままでは解決できない大きな問題を小さな問題に分割し、その全てを解決することで、最終的に最初の問題全体を解決する、という問題解決の手法

分割統治はパターンではなく、問題解決プロセスを考えるための思考法的側面が強い

分割統治を使って問題解決する手順は下記二つに分かれる

1. 基本ケースを特定する。基本ケースはできるだけ単純なケースでは無ければならない

2. 基本ケースになるまで問題を分割する

分割統治の適用

Q.横幅が1680m 高さが640mの長方形があります。この長方形を、正方形の区画に均等に分割した場合の正方形の1辺の長さを求めよ。ただし、正方形の大きさが最も大きくなるようにしなさい

クイックソート

code:quick_sort.py

def sort(array):

if len(array) < 2:

return array

else:

第5章　関連付ければ話も早い：ハッシュテーブル

第6章　グラフを作れば見えてくる：幅優先探索

第7章　本からピアノへ物々交換大作戦：ダイクストラ法

ダイクストラ法とは何か

特定のノードから他の全てのノードへの最短経路を求めることができる

非負の重みを持つ有向または無向グラフに対して有効である

ダイクストラ法の実装

必要な要素

グラフの定義: ノード間の繋がりとコストをハッシュテーブルに格納

コストの定義: 初期状態で各ノードへのコストをハッシュテーブルに格納。未知のコストは無限大（inf）とする

親の定義: 各ノードへの最短経路での直前のノード（親ノード）をハッシュテーブルに格納

主な処理フロー

1. 未処理のノードの中から最小コストのノードを探す

2. 当該ノードから隣接するノードへの新しいコストを計算する

3. 新しいコストが現在のコストより小さい場合、コストと親ノードを更新する

4. 上記ステップを未処理のノードがなくなるまで繰り返す

実装

code:hash.py

# --------------------------------------------------

# グラフ（グラフ関係として、ノード間の繋がりとコストを持つ）

# --------------------------------------------------

graph = {}

# --------------------------------------------------

# コスト

# --------------------------------------------------

infinity = float("inf")

costs = {}

# --------------------------------------------------

# 親

# --------------------------------------------------

parents = {}

code:main.py

# --------------------------------------------------

# ダイクストラ法を使った最短経路探索

# --------------------------------------------------

processed = [] # 処理済みのノードを格納する箱を用意

node = find_lowest_cost_node(costs) # まだ処理していない最小のコストのノードを探す

while node is not None:

# このノードの隣接ノードをループで回す

for neighbor_key in neighbors.keys():

# このノード経由で隣接ノードに移動するコストの方が低い場合

# 処理済みノードを更新する

processed.append(node)

# まだ処理が完了してない最もコストが低いノードを、次に処理するノードとして設定する

node = find_lowest_cost_node(costs)

code:common.py

# --------------------------------------------------

# 共通関数

# --------------------------------------------------

def find_lowest_cost_node(costs):

lowest_cost = float("inf")

lowest_cost_node = None

# すべてのノードをループする

for node in costs:

# まだ処理していない最小のコストのノードであれば

if cost < lowest_cost and node not in processed:

# 新たに最小のコストのノードとして設定する

lowest_cost = cost

lowest_cost_node = node

return lowest_cost_node

第8章　問題は続くよどこまでも：貪欲法

貪欲法とは何か

貪欲法の基本的アプローチ：

1.問題の最適化目標を定義する（例：最短経路探索の場合は「最も移動コストがかからない経路を選択」が該当）

2.現在の状況からスタートし、各ステップで最も有利な選択をする（例：最短経路探索の場合は「経路の選択」）

3.選択した解を部分解に追加する。

4.問題が解決されるまでステップ2とステップ3を繰り返す。

貪欲法の特徴

貪欲法は、各ステップでの最適な選択を行うため、局所的に最適な解を求めることができる。

しかし、貪欲法は全体として最適な解を保証するわけではない。なぜなら、貪欲法は各ステップでの最適な選択を行うために、将来の状況や選択の組み合わせについては考慮しないため、最終的な解が最適解となるとは限らないから。

ナップザック問題

集合カバー問題

NP完全問題

NP完全問題かどうかを見極めるには？

簡単にに見極める方法は無い

ただし、ヒントはいくつかある

第9章　ドロボーは計画的に：動的計画法

第10章　分類したら予測して：ｋ近傍法

第11章　この先にはなにがあるの？

第12章　答え合わせ