Was sind die zeitlichen Komplexitäten verschiedener Datenstrukturen?

Ich versuche, die zeitliche Komplexität von Operationen gängiger Datenstrukturen wie Arrays, binärer Suchbaum, Heap, verknüpfter Liste usw. aufzulisten, und beziehe mich insbesondere auf Java. Sie sind sehr häufig, aber ich denke, einige von uns sind nicht 100% sicher über die genaue Antwort. Jede Hilfe, insbesondere Referenzen, wird sehr geschätzt.

Beispiel: Für einfach verknüpfte Listen: Das Ändern eines internen Elements ist O (1). Wie kannst du das machen? Sie MÜSSEN das Element durchsuchen, bevor Sie es ändern. Für den Vektor wird das Hinzufügen eines internen Elements als O (n) angegeben. Aber warum können wir es nicht in amortisierter konstanter Zeit mit dem Index tun? Bitte korrigieren Sie mich, wenn mir etwas fehlt.

Ich poste meine Ergebnisse / Vermutungen als erste Antwort.

Arrays

• Set, Check Element an einem bestimmten Index: O (1)
• Suchen : O (n), wenn das Array unsortiert ist, und O (log n), wenn das Array sortiert ist und so etwas wie eine binäre Suche verwendet wird.
• Wie von Aivean hervorgehoben , ist Deletefür Arrays keine Operation verfügbar. Wir können ein Element symbolisch löschen, indem wir es auf einen bestimmten Wert setzen, z. B. -1, 0 usw., abhängig von unseren Anforderungen
• Ebenso ist Insertfür Arrays grundsätzlich Setwie eingangs erwähnt

Anordnungsliste:

• Hinzufügen : Amortisiertes O (1)
• Entfernen Sie : O (n)
• Enthält : O (n)
• Größe : O (1)

Verknüpfte Liste:

• Einfügen : O (1) , wenn am Kopf, O (n), wenn irgendwo anders, da wir diese Position erreichen müssen, indem wir die verknüpfte Liste linear durchlaufen.
• Löschen : O (1) , wenn am Kopf, O (n), wenn irgendwo anders, da wir diese Position erreichen müssen, indem wir die verknüpfte Liste linear durchlaufen.
• Suche : O (n)

Doppelt verknüpfte Liste:

• Einfügen : O (1) , wenn am Kopf oder Schwanz, O (n), wenn irgendwo anders, da wir diese Position erreichen müssen, indem wir die verknüpfte Liste linear durchlaufen.
• Löschen : O (1) , wenn am Kopf oder Schwanz, O (n), wenn irgendwo anders, da wir diese Position erreichen müssen, indem wir die verknüpfte Liste linear durchlaufen.
• Suche : O (n)

Stapel:

• Drücken Sie : O (1)
• Pop : O (1)
• Oben : O (1)
• Suche (so etwas wie Nachschlagen als spezielle Operation): O (n) (ich denke schon)

Warteschlange / Deque / Circular Queue:

• Einfügen : O (1)
• Entfernen Sie : O (1)
• Größe : O (1)

Binärer Suchbaum:

• Einfügen, Löschen und Suchen : Durchschnittlicher Fall: O (log n) , schlechtester Fall: O (n)

Rot-Schwarzer Baum:

• Einfügen, Löschen und Suchen : Durchschnittlicher Fall: O (log n) , schlechtester Fall: O (log n)

Heap / PriorityQueue (min / max):

• Find Min / Find Max : O (1)
• Einfügen : O (log n)
• Min löschen / Max löschen : O (log n)
• Extrakt Min / Extrakt Max : O (log n)
• Nachschlagen, Löschen (falls überhaupt angegeben): O (n) , wir müssen alle Elemente scannen, da sie nicht wie BST geordnet sind

HashMap / Hashtable / HashSet:

• Einfügen / Löschen : O (1) amortisiert
• Größe ändern / Hash : O (n)
• Enthält : O (1)