Ich werde das mit der Tatsache vortragen, dass ich mich nicht sehr gut mit Big O Notation auskenne, also denke ich vielleicht darüber nach.
Ich habe SO nach dem Zufallsprinzip durchsucht, als ich auf eine Frage zur Erkennung von Endlosschleifen in Linked Lists stieß. Dies hat mich auf den Algorithmus hier aufmerksam gemacht, der als Turtle and Rabbit bekannt ist.
%Vor%In dem Artikel erwähnt er, dass es O (N) ist. Aus dem, was ich verstehe, bedeutet O (N), dass die Geschwindigkeit des Algorithmus linear wächst in Bezug auf wie viele Elemente in der Liste sind.
Aber, solange ich nicht falsch sehe, überspringt die Kaninchenvariable immer einen Knoten (also ist sie "schneller"), was bedeutet, dass sie den Schildkrötenknoten überspringt und somit das Potential hat, um den Knoten herumzulaufen Endlosschleife 1 oder mehrmals, bevor sie der gleiche Knoten wie die Schildkrötenvariable wird, was bedeuten würde, dass das Worst-Case-Szenario nicht O (N) ist.
Vermisse ich etwas? Ich denke, eine Optimierung könnte sein, ob auch rabbit.Next.Equals(turtle) überprüft wird, aber da keiner der Kommentare darauf hinweist, frage ich mich, ob mir etwas fehlt.
Der Hase springt nie über die Schildkröte, weil der Unterschied zwischen der Geschwindigkeit 1 ist.
Der Hase geht zuerst in die Schleife, dann die Schildkröte. Sobald die Schildkröte in der Schleife ist, ist der Unterschied zwischen dem Hasen und der Schildkröte entschieden, und Sie können denken, dass der Hase hinter der Schildkröte ist. Dann wird die Differenz für jeden Schritt einfach um 1 verringert.
Also werden die Gesamtschritte N nicht überschreiten, und daher ist es O (n).
Eine kleine Handsimulation sollte dir zeigen, dass, während der Hase einmal über die Schildkröte springen kann, beim zweiten Mal um die Schleife herum (sozusagen) darauf treten wird. (BEARBEITEN: Dies gilt, sobald sowohl der Hase als auch die Schildkröte in der Schleife sind, was in höchstens O (N) Iterationen passieren wird.) Da O (2 * N) = O (N), ist es immer noch ein O (N) Algorithmus .
Netter Algorithmus auch. +1 für den Link.
Der Hase kann nicht über die Schildkröte springen, da sich auch die Schildkröte bewegt. In ASCII-Art:
%Vor%Anders gesagt, solange der Hase hinter der Schildkröte ist, verringert jede Iteration der Schleife ihren Abstand um 1. Daher wird es eine Iteration geben, bei der der Abstand genau 0 wird.
Dieser Algorithmus wird klarer, wenn Sie stattdessen den Hasen und die Schildkröte auf demselben Knoten starten. Wenn die Schildkröte N Knoten vorwärts bewegt hat, hat der Hase 2N Knoten voraus bewegt. Wenn es einen Zyklus der Länge N gibt, ist der Turle nach N Zügen zum Startpunkt zurückgekehrt, und die 2N Zügen des Hasen landen ebenfalls auf dem Startknoten, nachdem er die Schleife zweimal durchlaufen hat.
Es gibt zwei Situationen:
Betrachten wir beide.
In 1 haben wir das:
T R x x
dann
%Code%
dann
%Code%
dann
x T x R
In 2 haben wir das:
%Code%
dann
%Code%
dann
x R T x
Da der Hase und der Hase sich nur in maximal zwei Schritten bewegen können, sind dies die einzigen beiden Bedingungen, die es zu beachten gilt. Es gibt wahrscheinlich einen richtigen induktiven Beweis hier, aber das Zeigen der Phasen erklärt, warum das funktioniert, selbst wenn der Hase die Schildkröte überspringt. Der Hase kann die Schildkröte nur überspringen, wenn er hinter der Schildkröte ist, und wenn er hinter der Schildkröte ist, wird er entweder nicht überspringen oder er wird kollidieren.
Wenn der Hase die Schildkröte überspringt, wie in 1, brauchen wir nur x x x RT Bewegungen der Schildkröte und des Hasen, also T R x für N ist die Länge der Liste, das ist R T x