webentwicklung-frage-antwort-db.com.de

Komplexität von Multiset-, Map- und Hash-Maps

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

  • einfügen von Einträgen
  • zugreifen auf Einträge
  • einträge abrufen
  • einträge vergleichen
67
Harry

map, Set, Multimap und Multiset

Diese werden mit einem rot-schwarzer Baum implementiert, einer Art ausgeglichener binärer Suchbaum . Sie haben folgende asymptotische Laufzeiten:

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

hash_map, hash_set, hash_multimap und hash_multiset

Diese werden mit Hash-Tabellen implementiert. Sie haben folgende Laufzeiten:

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

Wenn Sie eine ordnungsgemäße Hash-Funktion verwenden, werden Sie fast nie das Worst-Case-Verhalten bemerken. Beachten Sie jedoch Folgendes: Denial-of-Service über algorithmische Komplexitätsangriffe von Crosby und Wallach davon.

98
Adam Rosenfield

Sie finden diese Informationen in der SGI STL-Dokumentation: http://www.sgi.com/tech/stl/

Grundsätzlich sind sowohl Multiset als auch Maps sortierte Binärbäume, sodass das Einfügen/Finden von 1 aus N Einträgen O (log N) erfordert. Siehe Sortierte Zuordnung. Container in der Dokumentation.

Der große Vorteil von Hashmap ist natürlich O(1) zum Einfügen und Suchen von Einträgen.

Der Zugriff darauf, nachdem er gefunden wurde, ist O(1) für alle Strukturen. Vergleich, was meinst du damit? Klingt für mich nach O(1) alle wurden gefunden.

8
ypnos