フロイドのサイクル検出の実行時の複雑さ

Question

フロイドのサイクル検出アルゴリズムの実行時の複雑さを言及したオンラインソースによれば、O（n）です。 セイ、

p = slow pointer 
q = fast pointer 
m = the distance from start of linked list to first loop node 
k = the distance of the meeting point of fast and slow nodes from the first loop node 
l = length of loop 
rp = number of loop rotations by p before meeting q. 
rq = number of loop rotations by q before meeting p. 

実行時間の複雑さは、この値はO（N）であるどのよう= M + RP * 1 + K すべきですか？

Answer 1

リストは、次に< = NステップでNノードを有し、いずれか早くポインタがリストの終わりを見つける、またはそこループであり、低速ポインタはループになります。

ループの長さはM < = Nとなります。遅いポインタがループに入ると、高速ポインタと低速ポインタの両方がループ内で永久にスタックされます。各ステップでは、高速ポインターとスローポインターの間の距離は1だけ増加します。距離がMで割り切れる場合、高速ポインターとスローポインターは同じノード上にあり、アルゴリズムは終了します。距離は、Mで< = Mステップで割り切れる数に達するでしょう。

したがって、ループに遅いポインタを取得し、次に満たすために高速と低速のポインタを取得するには、< = N + M < = 2Nステップをとり、それがO（N）で

あります

実際には、ループがあるときに遅いポインタがN-Mのステップでそれに到達するので、合計ステップ数は< = Nであることに注意すれば、ステップ数に厳しい制限を設けることができます。

Answer 2

nノードがある場合、低速ポインタは、高速ポインタが低速ポインタと一致するか、またはリストの終わりを検出する前に、nステップを超えて移動することが保証されていません。つまり、遅いポインタを進める作業をO（n）し、速いポインタをO（n）の約2倍進めることを意味します。したがって、アルゴリズム全体はO（n）である。