Algorithmen und Datenstrukturen · Senior · Frage 42 von 75
Warum lässt sich binäre Suche auf einer verketteten Liste nicht effizient ausführen?
- 1Verkettete Listen lassen sich nicht sortiert halten
- 2Die Mitte zu erreichen kostet O(n), es gibt keinen wahlfreien Zugriff
- 3Binäre Suche braucht die Länge, und Listen haben keine
Antwort zeigen
Richtige Antwort: Die Mitte zu erreichen kostet O(n), es gibt keinen wahlfreien Zugriff
Erklärung
Binäre Suche beruht auf O(1)-Zugriff per Index. Auf einer Liste durchläuft jeder Halbierungsschritt die Hälfte der verbleibenden Knoten, insgesamt also O(n). Skip Lists fügen zusätzliche Zeiger hinzu, um O(log n) wiederherzustellen.