algorithm - フロイドのサイクル検索アルゴリズムで複数のノードをスキップする

Question

今日、リンクされたリストのループを検出するフロイドのアルゴリズムを読んでいました。ループ検出を高速化するために、複数のノード (たとえば 2 つ) をスキップした方がよいのではないかと思っていました。

例えば：

fastptr=fastptr->next->next->next.

変更中は副作用が考慮されることに注意してくださいfastptr。

Answer 1

あなたの提案はまだ正しいですが、それはアルゴリズムの速度を変えません。ウィキでカメとウサギのアルゴリズムを見てみると：

アルゴリズムの重要な洞察は、任意の整数i≥μおよびk≥0の場合、x _i = x _{i +kλ}です。ここで、λは検出されるループの長さであり、μはループの開始位置です。特に、i =kλ≥μの場合は常に、x _i = _x2iとなります。

太字の部分では、 x _i = x _3i、またはその他の係数と言うこともできますが、重要な洞察はiを見つけることです。ジャンプの数は重要ではなく、アルゴリズムの順序は、i。