Ist einsetzen Zeit, die Komplexität der sortierten-Liste der Implementierung der priority queue O(n)?

Vom wikipedia:

Sortierte Liste Implementierung: Wie ein
Kasse im Supermarkt, aber
wo wichtige Leute zu bekommen "cut" in
vor weniger wichtigen Leuten. (O(n)
einsetzen Zeit, O(1) get-next time,
O(n*log(n)) zu bauen)

Ich denke, wenn die Suche die Einfügeposition mit binäre Suche Algorithmus,der die Einfügung Zeit Komplexität O(log(n)).Hier behandle ich die Ankunft um von jobs als einen Faktor Priorität.

Also bin ich falsch oder wikipedia falsch ist?

Update:
Nach der strengen definition der Liste von TAOCP:

Einer linearen Liste ist eine Sequenz von n >=0
Knoten XEins, X[2], ... , X[n], deren
wesentliche strukturelle properities
beziehen Sie nur die relativen Positionen
zwischen den Elementen, wie Sie in einem
line.

Ich nehme an, die Liste wikipedia verweisen ist nicht verkettete Liste,und es könnte sein, array.

Dank.

  • Könntest du poste den link zu dem Wikipedia-Artikel, den du zitiert hast?
  • Ah, ich habe die Arbeit für Sie. Es ist die priority-queue-Artikel: en.wikipedia.org/wiki/Priority_queue
InformationsquelleAutor Jichao | 2010-02-01
  1. 3

    wenn der es ist verbunden mit Liste unterstützt Sie nicht tun können, binäre Suche, also;
    finden Sie die Einfügemarke ist O(n),
    eigentlich einfügen O(1) wie ändern Sie einfach die benachbarten Knoten,
    insgesamt O(n).

    wenn Ihr array gesichert, die Sie tun können eine binäre Suche also;
    finden Sie die Einfügemarke ist in O(log(n)),
    aber das einfügen in ein array ist O(n) müssen Sie möglicherweise verschieben Sie alle Elemente des Arrays,
    insgesamt O(n)

    dies ist, warum Sie eigentlich haben Baum/heap gesichert, so dass alle Operationen in O(log(n))

    • danke.ich habe nicht betrachten Sie die Bewegung von Knoten vor 🙂
    InformationsquelleAutor jk.
  2. 3

    Es scheint, dass in Ihrem Zitat, Wikipedia bezieht sich auf eine priority-queue unterstützt durch eine sortierte Liste, sondern als ein heap. Zum einfügen eines Elements in eine sortierte Liste benötigt O(n) Zeit (vorausgesetzt, dass wir die Aufrechterhaltung Ihrer sortedness).

    • I dont think so.Die Liste soll sortiert werden, bevor Sie die Einfügemarke. Das ist, warum die Zeit, die Komplexität von build-up ist O(n*log(n)) die Zeit ist, die Komplexität der general-sort-Algorithmus.
    • betrachten Sie die Liste 1 -> 2 -> 3 -> 4 und versuchen Sie element 5 in Sie es von hand. Beachten Sie, dass Sie nicht über random-access - (es gibt keine list[3] gibt es nur list->next)
    • ist nicht verketteten Liste.Es sind eben in der Regel entweder als verknüpfte Listen (entweder einzeln oder doppelt-verlinkten) oder als arrays.Also, wenn ich implementate die Priorität Baum als array,dann bekomme ich den wahlfreien Zugriff.
    • auch wenn Sie die Umsetzung Ihrer Liste als ein array, deine Aussagen sind falsch. Einfügen in ein array ist O(n) im worst-case und durchschnittlichen Fall, da müssen Sie die shift-allen voran der Elemente im array über den Punkt der Einfügung.
    InformationsquelleAutor danben
  3. 1

    Binäre Suche ist in der Tat O(log n) aber binäre Suche funktioniert auf arrays - es funktioniert in dieser Zeit, denn Sie können auf ein element in O(1).

    Jedoch in der Literatur, wenn Sie sehen, der Begriff-Liste, die Sie denken sollten verketteten Listen.
    In einer Liste, daher Sie nicht haben O(1) Zugriffszeit, sondern Sie brauchen, um die Suche für die position "von hand" - also einfügen eines Elements nehmen würde O(n).

    • auch wenn Sie ein array können Sie den Speicherort suchen in O(log(n)), aber das einfügen wird immer noch O(n) kopieren Sie nun das array
    • Aber array ist eine Art Liste auch.
    • Das ist der Punkt!
    • ein array ist nicht eine Art Liste; array-Elemente werden sequenziell im Speicher des Computers: es bedeutet, dass nach array[0] es ist immer array[1] im Speicher des Computers. Eine Liste der nicht über diese Einschränkung - zwischen der ersten und zweiten Elemente in einer Liste, es könnten auch andere Daten völlig ohne Verbindung zu es. Die Schlimmste Zeit-Komplexität des Algorithmus für das einfügen O(n) in beiden Fällen ist aber aus ganz anderen Gründen (und auf dem Papier - in ganz anderen Fällen - erwägen Sie 1 in der Liste 0->2->3->4 versus in der Reihe 0 2 3 4).
    • es ist etwas mehrdeutig, wenn einige Sprachen zu nennen, arrays, Listen, wäre es besser, ausdrücklich sagen, verkettete Liste, wenn es das ist, was gemeint ist, erweitert meinen Kommentar zu einer Antwort, als es scheint hilfreich zu sein
    InformationsquelleAutor laura
  4. 0

    Schlimmsten Fall einsetzen der Zeit in eine sortierte Liste O(n). Im schlimmsten Fall ist das einfügen die oberste Position in der Liste. Zu tun, dass Sie Schritt für Schritt durch alle Elemente, und fügen Sie anschließend am Ende. Der Grund, warum Sie nicht bekommen, es zu tun eine binäre Suche ist, dass nur das element, das Sie zugreifen können, in der Liste ist der Nachfolger von Ihre aktuelle element, D. H. ohne random-access.

    InformationsquelleAutor Joel
  5. 0

    Wikipedia korrekt ist. Wie andere hier schon gesagt haben, Listen sind nicht random-access, daher müssen Sie zu jedem Knoten zwischen A und B, bevor man zu B, und Das macht binäre Suche nutzlos, da das Durchlaufen der Liste ist O(n), so dass Sie am Ende tut mehr Arbeit, als wenn Sie gerade iteriert über die Liste einmal. Sie könnten cache-der Anfang, Mitte und Ende-Knoten, die in einem separaten Puffer-und überprüfen Sie diese zuerst. Das wäre aber nur die gleiche Wirkung wie die Verwendung mehrerer Listen. Die skip-Liste Datenstruktur nimmt diese Idee einen Schritt weiter.

    So verwenden Sie einen random-access-heap statt, oder vielleicht eine skip-Liste: http://en.wikipedia.org/wiki/Skip_list je nach Ihren Bedürfnissen.

    InformationsquelleAutor
Schreibe einen Kommentar