Was ist die Komplexität (groß-oh) für die remove() Funktion in der Priority Queue-Klasse in Java? Ich kann nichts dokumentiertes finden, ich denke es ist O (n), wenn man bedenkt, dass man das Element finden muss, bevor man es entfernt und dann den Baum neu mischt. aber ich habe andere gesehen, die anderer Meinung sind und denken, es ist O (logn). Irgendwelche Ideen?Priorität Queue Entfernung Komplexität Zeit
Die Komplexität für entfernen ist O (N), da die Komplexität für enthält, ist O (N) (in Prioritätswarteschlange Klasse java)
Eine Möglichkeit, dies kann in Ihre eigenen Priorität gemacht O (log N) werden Die Warteschlangenimplementierung soll eine Hilfsdatenstruktur wie eine HashMap verwalten, die die Zuordnungen von einem Wert in der Prioritätswarteschlange zu seiner Position in der Warteschlange beibehält. Also, zu jeder Zeit - Sie würden die Indexposition eines beliebigen Wertes kennen.
Beachten Sie, dass diese Änderung keinen Einfluss auf die Laufzeit der vorhandenen Vorgänge hat. Sie müssen die Zuordnungen nur während der Heap-Operationen aktualisieren.
Also, wenn ich die Indexposition eines Elements kenne, wie entferne ich es in der Priority Queue API basierend auf dem Index? (in O (logN) Zeit) – novalain
@novalain Leider bietet die Java-API keinen Zugriff auf Elemente in einer Prioritätswarteschlange nach Index. Daher müssen Sie Ihre eigene selbst erstellte Implementierung einer Prioritätswarteschlange verwenden. –
Wie kommt es, dass O (logN) von unserer eigenen Implementierung und nicht von O (1) entfernt wird? Ich bin mir sicher, dass mir einige Details fehlen, aber eine Prioritätswarteschlange ist nur eine Datenstruktur, die von hoher zu niedriger Priorität sortiert ist. Wenn es über eine verkettete Liste implementiert wird und wir den Index kennen, können wir nicht einfach dieses Element entfernen und den vorherigen Knoten mit dem folgenden Knoten verbinden? – user3125693
Laut Oracle-Dokumentation: „note Umsetzung: Diese Implementierung stellt O (log (n)) Zeit für die Enqueing und dequeing Methoden (Angebot, Umfrage, remove() und fügen); lineare Zeit für Die Methoden remove (Object) und object (Object) sowie die konstante Zeit für die Methoden zum Abrufen (peek, element und size). "
Ich denke, er meinte remove (object) nicht remove() das erste ist O (n), das letztere ist O (log n) –
'remove()' und 'poll()' sind die gleichen, mit Ausnahme der fehlenden Element Semantik. Das Entfernen eines bestimmten Elements ('remove (Object)') ist 'O (n)'. Ich denke, die Frage war nicht klar und das ist auch eine gültige Antwort ... – TWiStErRob
Die Verwirrung wird von Ihrer "entfernen" Funktion tatsächlich verursacht. In Java gibt es zwei Remove-Funktionen.
remove() -> Dies ist, um den Kopf/Wurzel zu entfernen, dauert es O (logN) Zeit.
entfernen (Objekt o) -> Dies ist ein beliebiges Objekt zu entfernen. Das Auffinden dieses Objekts dauert O (N), und das Entfernen dauert 0 (logN) Zeit.
Haben Sie darüber nachgedacht, den Javadoc zu lesen? ["Diese Implementierung bietet O (log (n)) Zeit für die Enque- und Dequeing-Methoden (offer, poll, remove() und add)"] (http://docs.oracle.com/javase/6/docs/api /java/util/PriorityQueue.html). – EJP
Ja, habe ich. In der nächsten Zeile heißt es: lineare Zeit für das Entfernen (Object) und enthält (Object) Methoden; und konstante Zeit für die Retrieval-Methoden (Peek, Element und Größe) ', wo ich verwirrt wurde. Ich denke, ich habe es jetzt aber. – samturner