【要約】Floydの循環検出で、2つのポインタがサイクルの入口で会う理由 [Zenn_Python] | Summary by TechDistill
> Source: Zenn_Python
Execute Primary Source
// Problem
アルゴリズムの実装において、開発者は「なぜ衝突後に特定の操作を行うと入口に辿り着けるのか」という直感に反する挙動に直面する。LeetCode等のコーディング問題や、低レイヤのデータ構造操作において、以下の課題が生じる。
- ・ポインタの移動速度（1歩と2歩）が衝突を保証する点は理解しやすい。
- ・衝突後に「先頭」と「衝突点」から1歩ずつ進める処理の数学的妥当性が不明瞭である。
- ・直感的な理解だけでは、エッジケースにおける挙動の保証が困難である。
// Approach
本記事では、ポインタの移動距離を数式化し、合同式を用いることで、衝突後の挙動を数学的に証明するアプローチをとっている。具体的なステップは以下の通りである。
- ・距離の定義：入口までの距離 $\mu$、サイクル長 $\lambda$、入口から衝突点までの距離 $x$ を定義する。
- ・衝突条件の立式：slowの移動距離 $t$ が $\lambda$ の倍数であることを導く。
- ・合同式の導出：$\mu + x \equiv 0 \pmod \lambda$ から $\mu \equiv -x \pmod \lambda$ を導く。
- ・入口への到達証明：衝突点から入口までの距離 $d$ が $\mu$ と合同であることを示し、両ポインタが入口で一致することを証明する。
// Result
開発者は、Floydの循環検出アルゴリズムにおける衝突後の処理が、数学的に正しいことを理解できる。これにより、以下の成果が得られる。
- ・アルゴリズムの動作原理に対する深い洞察。
- ・メモリ効率（空間計算量 $O(1)$）を維持したまま、確実にサイクルの入口を特定する実装の確信。
- ・複雑なポインタ操作におけるデバッグや検証の容易化。
Senior Engineer Insight
> 本アルゴリズムは、空間計算量 $O(1)$ を実現しており、メモリ制約の厳しいシステムにおいて極めて有用である。大規模なデータ構造を扱う際、ハッシュセット等を用いた $O(n)$ の空間消費は避けたい。数学的根拠に基づいた実装は、コードの信頼性を高める。ただし、ポインタ操作はバグを誘発しやすいため、ユニットテストによる境界条件の検証が不可欠である。