Diskussion:Hase-Igel-Algorithmus

Performance

"Im schlechtesten Fall (worst case performance) sind m + n / 2 Schritte notwendig, weil der Igel nicht weiter als bis zur Mitte des Zyklus gelangen kann bevor der Hase diese zum zweiten Mal passiert."

Ich behaupte einfach mal, das ist falsch. Angenommen die komplette Liste ist eine einzige Schleife (also m=0). Der Hase läuft doppelt so schnell wie der Igel, d.h. wenn der Hase am Ende der Schleife/Liste ist, ist der Igel in der Mitte. Zu diesem Zeitpunkt hat der Hase den Igel aber noch nicht eingeholt.

Korrigiert mich, falls ich mich irre. --84.59.102.147 19:57, 13. Dez. 2007 (CET)

Ich war nun einfach mal so frei den Artikel anzupassen.

Da ich zum ersten Mal einen Artikel bearbeitet habe, bitte ich um Nachsicht bei etwaigen Fehlern.

--84.59.121.198 11:58, 16. Dez. 2007 (CET)

Markieren als Alternative

Habe die verlinkte Quelle gelesen und verstehe trotzdem nicht, warum der Ansatz des Markierens pauschal nicht funktioniert. Solange niemand anders die Markierung "verpfuscht" gibt es doch kein Problem? -- 84.59.121.198, 12:58, 16. Dezember 2007

Es hat auch einige Zeit gedauert, bis ich dieses Problem verstanden habe. Die Sache ist die, dass die Markierungen nicht gelöscht, sondern initial auf nicht besucht gesetzt werden müssen. Und das funktioniert nicht zuverlässig - ich kann ja im Fall einer Schleife nicht wissen, ob ich nun alle erwischt habe. --TracksOnWax (Diskussion) 17:33, 18. Mai 2013 (CEST)

Ich verstehe es trotzdem nicht. Warum soll man erst explizit alle auf "nicht besucht" setzen? Das Problem ist doch eher, dass die referenzierten Daten normalerweise keine solche Markierungsmöglichkeit haben, wenn man sie nicht selbst zu diesem Zweck implementiert hat. (Wie "markiert" man z.B. eine Zahl, die in der Liste steht?) --84.75.58.180 11:02, 24. Feb. 2014 (CET)

Illustration zum Hase-Igel-Algorithmus

Sorry, ich bin (anscheinend) nicht blöd, aber die Illustration kann ich nicht verstehen. Wie liest man die, was soll damit erläutert werden? Den Algorithmus als solchen habe ich verstanden, kein Problem. Eine Illustration sollte aber das Verständnis des Textes erleichtern, nicht umgekehrt dieses voraussetzen. -- WernerPopken 17:25, 17. Jun. 2009 (CEST)

Ich möchte mich diesem Kommentar anschließen. Und: ich wundere mich, wieso das Bild immer noch in dem Artikel ist, obwohl der Kommentar schon seit 2009 auf ein Problem mit der Darstellung und deren fehlender Erläuterung hinweist.

worest case/best case

die laufzeit für 'worest case' und 'best case' sind momentan gleich im artikel (m+n), da stimmt doch irgendetwas nicht oder? (nicht signierter Beitrag von 80.108.184.159 (Diskussion) 17:11, 6. Feb. 2012 (CET))

Beleg für Artikelnamen?

Derzeit entält der Artikel genau einen Beleg, und dieser ist englischsprachig. Daher bitte ich um einen Beleg dafür, dass der Algorithmus auf Deutsch tatsächlich Hase-Igel heißt, und nicht z.B. Floyds-Zykel-Auffinden-Algorithmus. --GroupCohomologist (Diskussion) 16:35, 4. Jul. 2016 (CEST)

Implementationsfehler

In der C-Implementation im Artikel ist ein Fehler (die anderen Programmiersprachen habe ich nicht überprüft). Sie wird bei leeren Listen (d.h. root == NULL) einen Nullzeiger (nämlich eben root) dereferenzieren.

Korrekt wäre, den Teil if(hase) hase = hase->next; an den Anfang des Schleifenrumpfes zu verschieben, die Anweisung hase = root->next; unmittelbar vor der Schleife durch hase = root; zu ersetzen und das Schleifenkriterium hase != igel als if (hase == igel) break; hinter if(hase) hase = hase->next; zu verlegen. --95.112.187.14 18:58, 11. Okt. 2019 (CEST)