Komplexität von Multiset, Map und Hash Map

Question

Ich möchte die Komplexität in Big O Notation der STL Multiset, Map und Hash Map Klassen wissen, wenn:

• Einträge einfügen
• Zugriff auf Einträge
• Abrufen von Einträgen
• Einträge vergleichen

Answer 1

Karte, Menge, Multikarte und Multiset

Diese werden mit Hilfe eines rot-schwarzer Baum , eine Art von balancierter binärer Suchbaum . Sie haben die folgenden asymptotischen Laufzeiten:

Einfügung: O(log n)
Nachschlagen: O(log n)
Löschung: O(log n)

hash_map, hash_set, hash_multimap und hash_multiset

Diese werden implementiert durch Hash-Tabellen . Sie haben die folgenden Laufzeiten:

Einfügung: O(1) erwartet, O(n) schlimmster Fall
Nachschlagen: O(1) erwartet, O(n) schlimmster Fall
Löschung: O(1) erwartet, O(n) schlimmster Fall

Wenn Sie eine geeignete Hash-Funktion verwenden, werden Sie den schlimmsten Fall fast nie erleben, aber es ist etwas, das man im Hinterkopf behalten sollte - siehe Denial of Service durch Angriffe auf die algorithmische Komplexität von Crosby und Wallach, um ein Beispiel dafür zu geben.

Answer 2

Für einstellen. , Multiset , Karte , multimap die Zeitkomplexität für das Einfügen, Löschen und Abrufen von Informationen ist O(logn) da sie zur Strukturierung der Daten dem Gleichgewichts-Binärbaum folgen.

Für ungeordneter_satz y unsortierte_karte , Hashing Methode wird zur Strukturierung der Daten verwendet. Die Zeitkomplexität hierfür ist also O(1) . Dies ist der perfekte Weg, um beliebige Operationen mit Informationen durchzuführen, wenn die Daten nicht in sortierter Reihenfolge vorliegen müssen.