Python実装ノート: アルゴリズムとデータ構造

このページでは、第5章〜第8章に対応する実装の読み方を整理する。

再帰のトレース

対象ファイル:

examples/python/recursion_trace.py

見るべき点:

• 停止条件があるか。
• 引数が停止条件へ近づいているか。
• 戻り値をどの順序で組み立てているか。

最小例:

def factorial(n: int) -> int:
    if n == 0:
        return 1
    return n * factorial(n - 1)

証明では、n=0 を基底部、n>0 のときを帰納ステップとして扱う。

BFS

対象ファイル:

examples/python/bfs_layers.py

BFS の目的は、無重みグラフで始点からの最短距離を求めることである。スタックではなくキューを使う点が重要である。

BFS の不変条件:

すでにキューから取り出された頂点の距離は確定している。

Union-Find

対象ファイル:

examples/python/union_find.py

Union-Find は、同値関係が作る同値類を動的に管理するデータ構造として読むと理解しやすい。

操作:

計算量をコードで確認する場合の注意

測定時間は OS、CPU、Python実装、入力生成に依存する。したがって、理論教材では測定値よりも、操作回数の式を作ることを優先する。

例えば二重ループなら、まず次を数える。

内側の処理が何回実行されるか。

その上で、総和を使って Θ 記法に落とす。