リンクされたリストでループを見つけるアルゴリズムについて話している質問をすでに見ました。私はフロイドのサイクル発見アルゴリズムの解決策を読んだことがあります. 1 つのポインター (遅い/亀) が 1 増加し、他のポインター (速い/うさぎ) が 2 増加します。それらが等しい場合、ループが見つかり、より速いポインターが null に達すると、リンクされたリストにループはありません。
ここで私の質問は、なぜ高速ポインターを 2 ずつ増やすのかということです。結果を得るには、2 ずつ増やす必要があります。または、X だけ増やすこともできます。より速いポインターを 2 ずつインクリメントする場合にループを見つける必要がありますか、または 3 または 5 または x ずつインクリメントする必要がある場合があります。
正確性の観点からは、数字の 2 を使用する必要がある理由はありません。どのステップ サイズを選択しても機能します (もちろん 1 つを除く)。ただし、サイズ 2 のステップを選択すると、効率が最大化されます。
これを理解するために、そもそもフロイドのアルゴリズムが機能する理由を見てみましょう。アイデアは、リストの先頭から始めて次に最後まで歩き続けます。リストにサイクルが含まれていない場合、これらの値はすべて別個のものです。ただし、サイクルが含まれている場合、このシーケンスは際限なく繰り返されます。
フロイドのアルゴリズムを機能させる定理は次のとおりです。
任意の正の整数 k に対して x j = x jkとなるような正の整数 j が存在する場合にのみ、連結リストに循環が含まれます。
これを証明してみましょう。それほど難しくありません。「if」の場合、そのような aj が存在する場合、k = 2 を選択します。次に、正の j の場合、x j = x 2jおよび j ≠ 2j であるため、リストにはサイクルが含まれます。
もう一方の方向については、位置 s から始まる長さ l のサイクルがリストに含まれていると仮定します。j を s より大きい l の最小倍数とします。次に、任意の k について、x jと x jkを考慮すると、j はループ長の倍数であるため、x jkは、リスト内の位置 j から始まり、j ステップ k-1 を取ることによって形成される要素と考えることができます。回。しかし、j のステップを実行するたびに、j はループの長さの倍数であるため、リストの最初の場所に戻ってしまいます。したがって、 x j = x jkです。
この証明により、各反復で一定数のステップを実行すると、実際に遅いポインターに到達することが保証されます。より正確には、各反復で k ステップを実行している場合、最終的に点 x jと x kjが見つかり、サイクルが検出されます。直感的には、実行時間を最小化するために k = 2 を選択する傾向があります。これは、反復ごとのステップ数が最も少ないためです。
次のように、ランタイムをより形式的に分析できます。リストにサイクルが含まれていない場合、n はリスト内の要素の数です。それ以外の場合、2 つのポインターは、低速ポインターが j ステップを実行した後に一致します。j は、s より大きい l の最小の倍数であることに注意してください。s ≤ l の場合、j = l; それ以外の場合、s > l の場合、j は最大で 2s になるため、j の値は O(s + l) になります。l と s はリスト内の要素の数を超えることはできないため、これは j = O(n) を意味します。ただし、低速ポインターが j ステップを実行した後、高速ポインターは、低速ポインターが実行した j ステップごとに k ステップを実行するため、O(kj) ステップを実行することになります。j = O(n) であるため、正味の実行時間は最大でも O(nk) です。これは、高速ポインターで実行するステップが多いほど、アルゴリズムが完了するまでに時間がかかることを示していることに注意してください (ただし、比例的にのみ)。したがって、k = 2 を選択すると、アルゴリズムの全体的な実行時間が最小限に抑えられます。
お役に立てれば！
サイズ L のサイクルを考えてみましょう。つまり、k 番目の要素でループがある場所を意味します: x k -> x k+1 -> ... -> x k+L-1 -> x k。1 つのポインターがレート r 1 =1 で実行され、もう 1 つのポインターが r 2で実行されるとします。最初のポインターが x kに到達すると、2 番目のポインターは既にループ内の要素 x k+s (0 <= s < L) にあります。さらに m ポインターをインクリメントした後、最初のポインターは x k+(m mod L)にあり、 2 番目のポインターは x k+((m*r 2 +s) mod L)にあります。したがって、2 つのポインターが衝突する条件は、合同を満たす m の存在と言い換えることができます。
m = m*r 2 + s (mod L)
これは、次の手順で簡略化できます
m(1-r 2 ) = s (mod L)
m(L+1-r 2 ) = s (mod L)
これは線形合同の形です。s が gcd(L+1-r 2 ,L)で割り切れる場合、解は m になります。これは、gcd(L+1-r 2 ,L)=1の場合に当てはまります。ｒ２＝２の場合、ｇｃｄ（Ｌ＋１－ｒ２，Ｌ）＝ｇｃｄ（Ｌ－１，Ｌ）＝１であり、解ｍは常に存在する。
したがって、r 2 =2 には、任意のサイクル サイズ L に対して gcd(L+1-r 2 ,L)=1 を満たすという優れた特性があり、2 つのポインターが異なる位置から開始する場合でも、ポインターが最終的に衝突することが保証されます。r 2の他の値には、この特性はありません。
高速ポインターが3ステップを移動し、低速ポインターがステップで移動する場合、1偶数のノードを含むサイクルで両方のポインターが一致することは保証されません。ただし、スローポインターが2段階的に移動した場合、会議は保証されます。
一般に、ウサギがHステップで移動し、カメがステップで移動するT場合、 iff のサイクルで会うことが保証されますH = T + 1。
カメに対してうさぎが動いているとします。
H - T反復あたりのノード数です。length のサイクルが与えられた場合N =(H - T) * k、kは任意の正の整数であり、うさぎはすべてのノードをスキップしH - T - 1(ここでも亀と比較して)、亀がそれらのノードのいずれかにあった場合、それらが出会うことは不可能です。
会議が保証される唯一の可能性は、H - T - 1 = 0.
したがって、x低速ポインタが だけ増加する限り、高速ポインタを だけ増加させることができx - 1ます。
リンクリストにループがある場合は、増分が2の高速ポインターの方がうまく機能し、増分が3または4以上になると、ループ内に入るとポインターが確実に衝突し、追い越しが発生しなくなります。
たとえば、3の増分を取り、ループ内で仮定する場合
fast pointer --> i
slow --> i+1
the next iteration
fast pointer --> i+3
slow --> i+2
一方、このような場合は2の増分では発生しません。
また、本当に運が悪ければ、ループの長さがでLあり、高速ポインタを。だけインクリメントしている状況に陥る可能性がありますL+1。そうすると、速いポインターと遅いポインターの動きの差が常にになるので、無限に立ち往生しますL。
私は自分自身を明確にしたいと思います。