Warum Zeiger erhöhen durch zwei, während der Suche nach loop in der verlinkten Liste, warum nicht 3,4,5?

Hatte ich einen Blick auf Frage bereits die Diskussion über Algorithmus zu finden, der in einer Schleife in einer verknüpften Liste. Ich habe gelesen, - Floyd-Zyklus-finding Algorithmus Lösung, erwähnt, dass die Menge von Orten, dass wir zwei Zeiger. Ein Zeiger( langsamer/Schildkröte ) wird um eins erhöht und der andere Zeiger( schneller/Hase ) erhöht sich um 2. Wenn Sie gleich sind, finden wir die Schleife und wenn schneller Zeiger erreicht null-es gibt keine Schleife, die in der verknüpften Liste.

Nun meine Frage ist, warum wir schneller zunehmen Zeiger 2. Warum nicht etwas anderes? Die Erhöhung von 2 notwendig ist, oder wir können Sie zu erhöhen, indem Sie X, um das Ergebnis zu erhalten. Ist es notwendig, dass finden wir eine Schleife, wenn wir die Schrittweite Zeiger schneller durch 2 oder es kann der Fall sein, wo wir brauchen, um die Schrittweite von 3 oder 5 oder x.

Leider werden Artikel wie der erste link zu (floyd-Algorithmus) ist geschrieben von Menschen, die nicht allzu besorgt über den Unterricht mit anderen zu verstehen, wie der Algorithmus. Ich kann akzeptieren, dass der Algorithmus funktioniert, aber ich habe noch zu finden, ein gutes Englisch Beschreibung von warum es funktioniert. Hoffentlich ist diese Antwort bekommen, Beschreibung.
gleiche ist der Fall mit mir, ich verstehe, es funktioniert aber nicht verstehen, wie und was ist die Logik hinter diesem.
Werfen Sie einen Blick auf Brent ' s Algorithmus, ist es sowieso besser.

InformationsquelleAutor GG. | 2011-02-26

  1. 48

    Gibt es keinen Grund, dass Sie müssen verwenden Sie die Nummer zwei. Jede Wahl der Schrittweite wird funktionieren (außer, natürlich).

    Zu sehen, warum dies funktioniert, lassen Sie uns nehmen einen Blick auf, warum Floyd ' s Algorithmus funktioniert in den ersten Platz. Die Idee ist, zu denken über die Reihenfolge, x0, x1, x2, ... xn, ..., die Elemente der verketteten Liste, die du besuchen wirst, wenn Sie an den Anfang der Liste und dann weiter zu Fuß nach unten, bis Sie das Ende erreichen. Wenn in der Liste nicht enthalten einen Zyklus, dann alle diese Werte sind deutlich. Wenn es enthält einen Zyklus, wenn, dann diese Sequenz wird endlos wiederholt.

    Hier ist das theorem, das macht Floyd ' s Algorithmus:

    Die verlinkte Liste enthält einen Zyklus, wenn, und nur wenn es eine positive ganze Zahl j, so dass für jede positive ganze Zahl k, xj = xjk.

    Gehen wir beweisen dies; es ist nicht so schwer. Für die "wenn" - Fall, falls ein solches j existiert, pick k = 2. Dann haben wir, dass für einige positive j, xj = x2j - und j ≠ 2j, und so enthält die Liste einen Zyklus.

    Für die andere Richtung nehmen wir an, die Liste enthält einen Zyklus der Länge l, beginnend an position s. Lassen j das kleinste Vielfache von l größer als s ist. Dann ist für alle k, wenn wir Bedenken, xj und xjk, da j ein Vielfaches von der loop-Länge, die wir denken können xjk als element gebildet, indem, beginnend an position j in der Liste, dann nehmen j die Schritte k-1 Zeiten. Aber jede dieser Zeiten, die Sie nehmen j die Schritte, die Sie am Ende wieder da, wo Sie begann, in die Liste, weil j ein Vielfaches von der loop-Länge. Folglich, xj = xjk.

    Dieser Nachweis garantiert Ihnen, dass wenn Sie eine Konstante Anzahl von Schritten, die bei jeder iteration, werden Sie in der Tat trifft den langsamen Zeiger. Genauer gesagt, wenn man unter k die Schritte, die bei jeder iteration, dann Sie werden schließlich feststellen, dass die Punkte xj und xkj und erkennt den Zyklus. Intuitiv neigen die Menschen zu wählen k = 2 zu minimieren, die Laufzeit, da nehmen Sie die geringste Anzahl von Schritten, die bei jeder iteration.

    Können wir analysieren die Laufzeit mehr formal wie folgt. Wenn in der Liste nicht enthalten einen Zyklus, dann der schnelle Zeiger auf das Ende der Liste nach n Schritten für O(n) Zeit, wobei n die Anzahl der Elemente in der Liste. Ansonsten, die zwei Zeiger treffen nach der langsamen Zeiger genommen hat j Schritte. Denken Sie daran, dass j das kleinste Vielfache von l größer als s ist. Wenn s ≤ l, dann ist j = l; andernfalls, wenn s > l, dann ist j werden bei den meisten 2s, und so der Wert von j ist O(N + l). Da l und s nicht größer sein kann als die Anzahl der Elemente in der Liste, das heißt als j = O(n). Jedoch, nach der langsamen Zeiger genommen hat j Schritte, die schnell pointer genommen haben, k die Schritte für jede der j Schritte, die der langsamere Zeiger, so wird es genommen haben O(kj) Schritte. Da j = O(n), die Netto-Laufzeit ist höchstens O(nk). Beachten Sie, dass dieser sagt, dass je mehr Schritte, die wir ergreifen, mit den fast-Zeiger, je länger der Algorithmus dauert, bis er fertig (wenn auch nur anteilig). Kommissionierung k = 2 somit minimiert sich die Laufzeit des Algorithmus.

    Hoffe, das hilft!

    Nicht Ihr Nachweis setzt Voraus, dass Sie wissen, die Länge des Zyklus, die Sie versuchen, zu finden, so dass Sie können wählen Sie eine geeignete Geschwindigkeit für den Hasen. Während dies wird produzieren ein Hase, der wird immer Arbeit für Sie, dass die Länge des Zyklus, wäre es nicht garantiert, um zu arbeiten für einen Zyklus von unterschiedlicher Länge (es sei denn, Sie wählten die Geschwindigkeit 2).
    Der Beweis selbst nicht davon ausgehen, dass Sie wissen, der Zyklus der Länge; es sagt nur, dass für jeden Zyklus und der Zyklus-Startposition es gibt eine position j mit der gewünschten Eigenschaft. Wenn Sie überlegen, wie das geändert tortise/Hase-Algorithmus funktionieren würde, wäre es zu Beginn voran die zwei Zeiger auf Sätze 1 und k. Nach der Einnahme von j Schritten, die zwei Zeiger wäre an den Positionen j und jk, die sind deckungsgleich. Sie brauchen nicht zu wissen, was j ist, um es zu erreichen. Macht das Sinn?
    Rybak - Das ist wahr. Die Laufzeit dieses Algorithmus ist proportional zu der Schrittweite, das ist der Grund, warum wir in der Regel wählen Sie 2.
    Wer downvoted - können Sie erklären, was ist falsch an dieser Antwort?
    Schöne Erklärung. Nach dem Start bei "Let' j das kleinste Vielfache von l größer als s" für einen Moment, es hat geklingelt: dies bedeutet, dass, wenn Sie nehmen j die Schritte von Anfang an, sind Sie innerhalb der Schleife (da j > s), und wenn du eine andere j Schritte von dort werden Sie wind-up wieder an der gleichen Stelle (da j ein Vielfaches von l ist). Also das gleiche muss halt für ein Vielfaches von j Schritte. Und obwohl wir nicht wissen, was j ist a priori, wir wissen, es muss existieren, und wir effektiv Fragen "Ist das j?" nach jedem Zug, so können wir es nicht verpassen.

    InformationsquelleAutor templatetypedef

  2. 32

    Lassen Sie uns annehmen, dass die Länge der Liste, die nicht enthalten die Schleife sein s, die Länge der Schleife werden t und das Verhältnis von fast_pointer_speed zu slow_pointer_speed werden k.

    Lassen Sie die zwei Zeiger treffen sich in einer Entfernung j aus dem Anfang der Schleife.

    So, den Abstand langsam Zeiger reist = s + j. Entfernung der fast-Zeiger-Reisen = s + j + m * t (wo m ist die Anzahl der Zeiten, der schnelle Zeiger abgeschlossen hat, die Schleife). Aber der schnelle Zeiger hätte auch eine Wegstrecke zurückgelegt k * (s + j) (k mal die Entfernung von der slow-Zeiger).

    Daher bekommen wir k * (s + j) = s + j + m * t.

    s + j = (m /k-1)t.

    Daher aus der obigen Gleichung, Länge der Zeiger langsam fährt ist ein ganzzahliges Vielfaches von der loop-Länge.

    Für größte Effizienz , (m /k-1) = 1 (der langsame Zeiger sollte nicht zurückgelegt haben der Schleife mehr als einmal.)

    daher m = k - 1 => k = m + 1

    Seit m ist das nicht.Zeiten der fast-Zeiger abgeschlossen ist, wird der loop -m >= 1 .
    Für größte Effizienz , m = 1.

    daher k = 2.

    wenn wir einen Wert von k > 2 mehr der Abstand der beiden Pointer hätte, um zu Reisen.

    Hoffe, diese Erklärung hilft.

    einfache und exzellente proof
    Wenn Sie Verhältnis der Geschwindigkeiten von Zeigern ist es nicht möglich, dass langsamer auch haben können, Durchlaufen die Schleife mehr als einmal damit, die Strecke durch langsamere möglich, nicht nur die s+j. Sagen wir langsamer bewegt man sich 2 Schritte einmal und schneller bewegt man sich in 5 Schritten. Bin ich etwas fehlt?
    Ja . Das ist wahr . Wenn man das Verhältnis von 2 , dann die kürzere Zeiger nicht brauchen, zu Durchlaufen die Schleife mehr als einmal und daher optimal ist . Das ist, was ich versucht habe zu beweisen . Anderen Verhältnissen , als Sie darauf hingewiesen , sind nicht optimal und der kürzere Zeiger möglicherweise, Durchlaufen die Schleife mehr als einmal.
    Können Sie sagen, warum in diese Gleichung: s + j = (m / k-1)t , (m,/k-1) sollte unbedingt eine ganze Zahl sein?
    Vielen Dank, das abschließend geklärt ist der Algorithmus für mich.

    InformationsquelleAutor Sumit Das

  3. 5

    Überlegen, einen Zyklus der Größe L, das heißt an der kth element ist, wo die Schleife ist: xk -> xk+1 -> ... -> xk+L-1 -> xk. Angenommen, ein Zeiger run at rate r1=1 und die andere bei r2. Wenn der erste Zeiger erreicht, xk der zweite Zeiger wird schon in der Schleife ein element xk+s, wobei 0 <= s < L. Nach m Zeiger inkrementiert den ersten Zeiger bei xk+(m mod L) und der zweite Zeiger ist bei xk+(m*r2+s) mod L). Daher die Bedingung, dass die zwei Zeiger miteinander kollidieren, können so formuliert werden, wie die Existenz eines m die Befriedigung der Kongruenz

    m = m*r2 + s (mod L)

    Dieser kann vereinfacht werden, mit den folgenden Schritten

    m(1-r2) = s (mod L)

    m(L+1-r2) = s (mod L)

    Dies ist die form einer linearen Kongruenz. Es hat eine Lösung m, wenn N ist teilbar durch ggT(L+1-r2 - L). Das wird sicherlich der Fall, wenn gcd(L+1-r2,L)=1. Wenn r2=2 ist, dann ist gcd(L+1-r2,L)=gcd(L-1,L)=1 und eine Lösung m immer vorhanden ist.

    Somit r2=2 hat die gute Eigenschaft, dass für jeden Zyklus der Größe L, es erfüllt gcd(L+1-r2,L)=1 und somit garantiert, dass die Zeiger irgendwann miteinander kollidieren, auch wenn die beiden Zeiger start an verschiedenen Orten. Andere Werte von r2 nicht diese Eigenschaft haben.

    Sehr interessant, dass ein double-speed-Hase hat diese zusätzliche "start-und-überall" - Eigenschaft. Ich brauche, um zu verstehen, modulare Arithmetik besser (ich habe alles verstanden, außer "Es wurde eine Lösung von m, wenn N ist teilbar durch ggT(L+1-r2,L)")

    InformationsquelleAutor user782220

  4. 2

    Wenn der Zeiger schnell bewegt 3 Schritte und langsame Zeiger auf 1 Schritt, es ist nicht garantiert, für beide Zeiger zu treffen, die in Zyklen mit einer geraden Anzahl von Knoten. Wenn der Zeiger langsam bewegt 2 Schritte, aber das treffen wäre garantiert.

    Im Allgemeinen, , wenn der Hase bewegt sich mit H Schritte, und die Schildkröte bewegt sich mit T Schritte, Sie werden garantiert, um ein treffen in einem Zyklus iff H = T + 1.

    Betrachten der Hase bewegt sich relativ zu der Schildkröte.

    • Hase Geschwindigkeit relativ zu der Schildkröte ist H - T Knoten pro iteration.

    • Gegeben ein Zyklus der Länge N =(H - T) * k, wo k ist jede positive
      integer, der Hase würde überspringen, jedes H - T - 1 Knoten (wieder relativ
      die Schildkröte), und es wäre unmöglich für Sie zu treffen, wenn
      die Schildkröte war in einem dieser Knoten.

    • Die einzige Möglichkeit, wo ein treffen ist garantiert, wenn H - T - 1 = 0.

    Daher, die Erhöhung der schnell-Zeiger von x ist erlaubt, solange der slow-Zeiger wird erhöht, indem x - 1.

    InformationsquelleAutor John Bupit

  5. 0

    Wenn es eine Schleife (mit n Knoten), dann, wenn ein Zeiger in die Schleife, Sie wird dort bleiben für immer; so bewegen wir uns vorwärts in der Zeit, bis beide Zeiger sind in der Schleife. Von hier aus auf den Zeiger dargestellt werden können, durch ganze zahlen modulo n mit den Anfangswerten a und b. Die Voraussetzung für Sie, um sich nach t Schritten ist dann

    +t≡b+2t mod n
    die Lösung t=a−b mod n.

    Dies funktioniert so lange, wie die Differenz zwischen den Geschwindigkeiten Aktien keine Primfaktoren mit n.

    Referenz
    https://math.stackexchange.com/questions/412876/proof-of-the-2-pointer-method-for-finding-a-linked-list-loop

    Die einzige Einschränkung auf Drehzahlen ist, dass der Unterschied sollte sein co-prime mit der loop-Länge.

    InformationsquelleAutor Peter

  6. -1

    Wenn die verlinkte Liste hat eine Schleife, dann eine schnelle Zeiger mit Schrittweite von 2 wird besser funktionieren, dann sagen Schrittweite von 3 oder 4 oder mehr, denn es sorgt dafür, dass sobald wir im inneren der Schleife wird der Zeiger wird sicherlich kollidieren, und es wird kein überholen.

    Zum Beispiel, wenn wir das Inkrement 3 und innerhalb der Schleife können davon ausgehen 

    fast pointer --> i  
slow         --> i+1 
the next iteration
fast pointer --> i+3  
slow         --> i+2

    in der Erwägung, dass ein solcher Fall nie passieren wird mit der Schrittweite von 2.

    Auch wenn Sie wirklich Pech haben, dann können Sie am Ende in einer situation, wo die loop-Länge ist L und Sie erhöht die schnelle Zeiger L+1. Dann werden Sie stecken unendlich, da der Unterschied der Bewegung, der schnellen und langsamen Zeiger wird immer L.

    Ich hoffe das ich mich klar genug ausgedrückt.

    Auch wenn die loop-Länge ist L, es ist OK, um die Schrittweite der schnelle Zeiger von L+1. Es wird wind-up in der gleichen Stelle jeder Zeit, aber das ist nicht ein problem, weil der langsame Zeiger fangen.
    wie kann slow-Zeiger jemals fangen die Zeiger schnell ?? der Unterschied zwischen den beiden wird immer konstant sein ... da es sein wird, beide werden um 1 erhöht.
    Kann T-Hilfe aber Kommentar auf diesen alten thread 🙂 beide fangen sich gegenseitig die gleiche Weise die Sekunden und Minuten Hände haben schließlich treffen einander auf einer Uhr Gesicht.

    InformationsquelleAutor ajayg

Schreibe einen Kommentar