wake-up-neo.com

wie kann ich die binäre Suche O (log n) in einer sortierten verketteten Liste anwenden?

Vor kurzem stieß ich auf eine interessante Frage in der verlinkten Liste. Eine einzeln verknüpfte Liste wird angegeben und wir müssen ein Element aus dieser Liste suchen. 

Zeitkomplexität sollte nicht mehr als O(log n) sein. Anscheinend müssen wir die binäre Suche auf diese verknüpfte Liste anwenden. Wie? Da die verknüpfte Liste keinen Direktzugriff bietet, wenn wir versuchen, den binären Suchalgorithmus anzuwenden, wird O(n) erreicht, da wir die Länge der Liste suchen und in die Mitte gehen müssen.

Irgendwelche Ideen? 

34
u449355

Mit einer einfachen, einfach verknüpften Liste ist das sicher nicht möglich.

Skizzennachweis: Um den letzten Knoten einer einfach verknüpften Liste zu untersuchen, müssen wir n-1-Operationen ausführen, um einem "nächsten" Zeiger zu folgen [Beweis durch Induktion auf die Tatsache, dass es nur einen Verweis auf den k+1-ten Knoten gibt, und dieser befindet sich im kth Knoten, und es dauert eine Operation, um ihm zu folgen]. Für bestimmte Eingaben muss der letzte Knoten untersucht werden (insbesondere, wenn das gesuchte Element gleich oder größer als sein Wert ist). Daher ist für bestimmte Eingaben die benötigte Zeit proportional zu n.

Sie benötigen entweder mehr Zeit oder eine andere Datenstruktur.

Beachten Sie, dass Sie dies in O (log n) Vergleiche mit einer binären Suche tun können. Es dauert nur mehr Zeit als das, also ist diese Tatsache nur dann von Interesse, wenn Vergleiche sehr viel teurer sind als das Durchlaufen von Listen.

38
Steve Jessop

Sie müssen Liste überspringen verwenden. Dies ist bei einer normalen verknüpften Liste nicht möglich (und ich möchte wirklich wissen, ob dies bei einer normalen Liste möglich ist). 

29
taskinoor

In verknüpfter Liste erreicht die binäre Suche möglicherweise keine Komplexität von O (log n), aber das wenigste kann durch Verwendung der Doppelzeigermethode, wie hier in dieser Forschungsarbeit beschrieben, etwas erreicht werden: http://www.ijcsit.com/docs /Volume%205/vol5issue02/ijcsit20140502215.pdf

2
sundar

Wie bereits erwähnt, ist dies im Allgemeinen nicht möglich. In einer Sprache wie C ist es jedoch möglich, wenn die Listenknoten zusammenhängend zugewiesen werden, die Struktur als ein Array von Knoten zu behandeln. 

Natürlich ist dies nur eine Antwort auf eine Trickfragevariante dieses Problems, aber das Problem ist immer eine Unmöglichkeit oder eine Trickfrage.

0
Marcin