Algorithmus der Hase und die Schildkröte

Der Floyd-Algorithmus-Zyklus-Erkennung, auch unter dem Namen des Algorithmus Hasen und der Schildkröte, ist ein Algorithmus zur Erkennung von Zyklen in beliebigen Sequenzen, ob Datenstrukturen oder Sequenzen on the fly im Raum O. generiert

Dieser Algorithmus wurde von Robert Floyd 1967 angegeben ist, und sollte nicht mit der Floyd-Warshall-Algorithmus zu verwechseln.

Algorithmus

Ist eine Funktion, und S eine endliche Menge der Mächtigkeit n. Nach betrachtet und definiert durch

Es ist klar, diese Suite zwangsläufig zu einem Zyklus führen, ist die Anzahl der möglichen Werte beschränkt auf n. Eine naive Möglichkeit, die Länge des Zyklus zu bestimmen, besteht darin, jedes Element der Sequenz zu speichern und auf jeder Stufe, um zu überprüfen, ob sich das neue Element unter den Elementen bereits aufgetreten. Der Raum verwendet wird, ist O, wobei μ ist die Zykluslänge λ und die Anzahl der Elemente außerhalb des Zyklus.

Wenn wir zwei Elemente in der Sequenz und derart, dass zu finden

ist dann ein Vielfaches der Zykluslänge.

Die Zykluserfassungs Floyd Algorithmus bestimmt diese Gleichheit durch gleichzeitiges Durchlaufen der Sequenz mit zwei verschiedenen Geschwindigkeiten bzw. 1 und 2. Der Algorithmus kann auf zwei gleichen Werten bestimmt, also M, so dass

Deshalb ist ein Vielfaches der Zykluslänge, um.

Um den genauen Wert von μ zu bestimmen, drehen Sie einfach den Wiederholungsalgorithmus von m + 1 eine andere Zahl, so dass zu finden. Daher war zum einen und zum anderen μ welche so teilt.

Visualisierung

Der beste Weg, um den Algorithmus zu visualisieren, um die Sequenz zu repräsentieren. Das resultierende Muster ähnelt dem griechischen Buchstaben ρ. Die Sequenz beginnt an der Unterseite, ansteigt und führt den Zyklus in Richtung im Uhrzeigersinn. Als nächstes wird der Floyd-Algorithmus, treffen sich die beiden Wege in nach 6 Iterationen. Eine zweite Runde des Algorithmus nimmt die beiden Kurse, um nach 6 neue Iterationen, also dem Wert entsprechen.

Bytecode

Wenn man den Wert zu erhalten wünscht, fügen Sie einfach den folgenden Code:

Komplexität

Der Algorithmus führt ein Minimum λ Vergleiche, da die langsamen Verlauf der Sequenz muss mindestens den Zyklus zu erreichen, um den schnellen Weg zu erfüllen. Die maximale Anzahl der Vergleiche ist, weil die langsame Strecke darf nicht mehr als eine Umdrehung des Zyklus zu machen, bevor sie von der schnellen Strecke gefangen. Der Algorithmus verwendet einen Raum O.

Varianten

Die bekannteste Variante der Zykluserfassungs Floyd-Algorithmus ist der Algorithmus rho Pollard, ein Zerlegungsalgorithmus Primfaktor Produkt, das die Pseudozufallsfolgen zur Faktorisierung ganzen Zahlen verwendet. Es gibt auch einen diskreten Logarithmus-Berechnungsalgorithmus auf der Grundlage des Zykluserfassungs Floyd-Algorithmus.

(0)
(0)
Kommentare - 0
Keine Kommentare

Fügen Sie einen Kommentar

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Zeichen übrig: 3000
captcha