Zeitkomplexität der Einfügung in verknüpfte Liste

Question

Entschuldigung Wenn sich diese Frage wie eine Lösungsprüfung anfühlt, wurde diese Frage jedoch in meinem Absolventen-Zulassungstest gestellt, und es gibt viel zu reiten:

Was ist der schlimmste Fall-Zeitkomplexität des Einfügens von $ N $ Elemente in eine leere verknüpfte Liste, wenn die verknüpfte Liste in sortierter Reihenfolge aufrechterhalten werden muss?

Meiner Meinung nach sollte die Antwort $ o (n ^ 2) $ sein, da wir in jedem Einfügen das Element an der richtigen Stelle einsetzen müssen und Es ist möglich, dass jedes Element an den letzten Ort eingefügt werden muss, was mir eine Zeitkomplexität von $ 1 + 2 + ... (N-1) + N= O (n ^ 2) $

jedoch die Lösung, die ich besagt, dass wir die Elemente in $ o (n \ log n) $ sortieren können, und dann können wir sie einfügen von einem in $ o (n) $ , geben uns eine allgemeine Komplexität von $ o (n \ log n) $ < / span>.

Von der gegebenen Formulierung der Frage, welche Lösung ist apt? Meiner Meinung nach neigt ich, da die Frage "Linked List in sortierter Reihenfolge" aufrechterhalten muss ", geneigt zu sagen, dass wir die Elemente nicht vorher sortieren und dann in der sortierten Reihenfolge einfügen.

Answer 1

Die Frage sagt nur, dass die Zielliste in sortierter Reihenfolge aufrechterhalten werden muss. Es sagt nichts über jede andere Datenstruktur, die Sie verwenden können. Die vorgeschlagene Lösung führt zuerst eine Vorverarbeitung der Argumente zum Einfügen, dann führt das Einfügen eignet. Dies ist von der Problemanweisung erlaubt.

Ein praktischer Grund dazu, dies zu tun, anstatt die Elemente einzufügen, dann wäre, wenn das verknüpfte Listenobjekt mit einem anderen Thread gemeinsam genutzt wird, der es erfordert, dass es immer sortiert ist. (In einem solchen Szenario müssen Sie sicherstellen, dass das Einfügen eines Elements atomar ist.) Diese Frage macht also nicht nur seltsame Anforderungen, um seltsam zu sein. Es ist die Art von Anforderungen, die in der echten Programmierung häufig auftreten.

Eine andere Lösung mit derselben Komplexität wäre, die Elemente in die Zielliste einzufügen, da sie gelangen, und halten Sie eine parallele Datenstruktur-Mapping-Elemente-Werte an Knotenzeiger in der Zielliste auf. Finden Sie das vorherige Element in der Zuordnung ein, um jedes Element einzufügen, und fügen Sie das neue Element nach diesem Knoten ein. Dies setzt voraus, dass der Einfügeprozess die List-Knoten erstellt, da er läuft (im Gegensatz zum Füllen vorhandener leerer Knoten).

Diese Frage ist mehr über das Leseverständnis als über Algorithmen. Die Art und Weise, wie es formuliert ist, ist es ein bisschen von einer Trickfrage. Es ist etwas schlecht formuliert, weil er sich auf ein präzises Lesen setzt, aber einige wichtige Annahmen angeben, z. B. der Tatsache, dass das Erhalten der Elemente zum Einfügen von Kosten $ O (n) $ , das Vergleichen von zwei Elementen kann in $ O (1) $ erfolgen, und die Eingabedomäne ist effektiv unbegrenzt (Übung: Kommen Sie mit einer $ O (n) $ Algorithmus Wenn die Eingänge Ganzzahlen im Bereich $ [1,42] $ ) sind. Die gegebene Antwort ist jedoch korrekt.

Sie haben davon ausgegangen, dass es keine Möglichkeit gibt, eine Hilfsdatenstruktur zu verwenden. Nichts in der Problemanweisung verbietet die Verwendung von Hilfsdatenstrukturen. Eine einfache Möglichkeit, Hilfsdatenstrukturen zu verbieten, erfordern den $ O (1) $ Speicheraufwandel.

Beachten Sie, dass Ihre Argumentation auch unter dieser Annahme falsch ist oder zumindest ungenau ist. Wenn Sie zufällig wissen, dass die Elemente in der richtigen Reihenfolge angegeben sind, können Sie einen Zeiger auf den Schwanz der Liste aufrechterhalten und dorthin einsetzen, was $ o (n) dauert $ . Der schlimmste Fall ist nicht, wenn jedes Element in der letzten Position in der Zielliste in die letzte Position eingefügt werden muss, aber in der letzten Position erreicht, wenn er die Liste in irgendeiner Weise durchquert. Der schlimmste Fall ist in der Tat $ \ theta (n ^ 2) $ , aber um dies zu beweisen, müssen Sie nachweisen, dass das Festlegen des Einfügungspunkts in der Liste $ \ theta (n) $ Time, und dies erfordert, dass die Entfernung von beliebiger -zeiger, die Sie in die Liste haben, nachfolgend durch $ \ omega (n) $ . Dies ist der Fall, wenn Sie eine konstante Anzahl $ A $ von Zeigern haben (Sie haben implizit angenommen $ A= 1 $ , mit einem einzelnen Zeiger zu Beginn der Liste), sodass Sie zumindest $ K / A $ -Knoten nach $ K $ Insertionen im schlimmsten Fall.

Answer 2

Bestmögliche Struktur, die ich kenne, sind Fibonacci-Haufen, Sie können Elemente in $ O (1) $ einfügen und das Minimum in $ o (\ \ \ \ \ \ log (n)) $ , das heißt, wenn Sie eine sortierte Reihenfolge aller Elemente benötigen, die Sie $ O (n \ log(n)) $ Beim Einfügen neuer Elemente kostet nur Sie $ O (1) $ , ich kenne keine andere Struktur, die mit diesem Schritt bleiben konnte.

Answer 3

Es ist wirklich eine knifflige Frage.Zunächst gilt die Komplexität von O (NLOGN) nur für die Algorithmen, die einen Vergleich zwischen ihren Elementen (Vergleichsalgorithmus) verwenden.Es gibt auch Algorithmen, die nicht vergleichend sind, wie beispielsweise Radix-Sort, die ihre Komplexität von der Größe in Bits abhängt, die die Zahlen im Speicher gespeichert werden müssen.Wenn wir also davon ausgehen, dass wir die Zahlen vorher mit einem Algorithmus sortieren können, können wir auch annehmen, dass die Zahlen natürlich sind, und das maximale Element ist M <10, also mit Radix-Sort, mit Radix-Sortieren Sie sich am schlimmsten Fall O (10n)= O (n).Wenn wir keine Annahme machen können, sind Sie richtig.Wenn Sie nur verknüpfte Listen verwenden dürfen und nichts weiter (keine Indexierung jeglicher Art), dann ist die Komplexität O (n ^ 2) (Bubble Sort).

Answer 4

Es sollte o (n) sein. Folgen Sie dem Algorithmus wie -

1) Wenn die verknüste Liste leer ist, dann machen Sie den Knoten als Kopf und zurückgeben.

2) Wenn der Wert des zu einfügierenden Knotens kleiner ist als der Wert des Kopfknotens, dann den Knoten einsetzen am Start und machen Sie den Kopf.

3) In einer Schleife finden Sie den entsprechenden Knoten danach welche der Eingangsknoten eingelegt werden soll.

, um den entsprechenden Knoten zu finden, der vom Kopf beginnt, Bewegen Sie sich weiter, bis Sie einen Knoten erreichen, der Wert ist größer als der Eingangsknoten.Der Knoten kurz davor ist das geeigneter Knoten

4) Setzen Sie den Knoten nach dem entsprechenden Knoten ein in Schritt 3

gefunden