Hallo,
Kann mir jemand sagen, welcher Komplexitäts-Klasse die Funktionen:
sorted(dict.keys()) und reversed(dict.keys)
angehören?
Komplexität von dict
-
BlackJack
Also `reversed(dict.keys)` ist O(1) → Das eine Methode nicht ”umgedreht” werden kann, wird in Konstanter Zeit festgestellt. Du meintest sicher `reversed(dict.keys())`
Ansonsten ist das sehr von der Implementierung von `reversed()` und `dict.keys()` abhängig. In CPython 2 vermute ich stark O(n) mit n der Anzahl der Schlüssel weil `keys()` eine Liste erstellt, in CPython 3 vermute ich stark O(1) weil `keys()` dort eine Objekt erstellt das eine Art `set`-Ansicht der Schlüssel ist und dabei nur eine Referenz auf die Daten des Wörterbuchs enthält. Aber vielleicht meintest Du ja *eigentlich* auch `list(reversed(dict.keys()))`…
Ansonsten ist das sehr von der Implementierung von `reversed()` und `dict.keys()` abhängig. In CPython 2 vermute ich stark O(n) mit n der Anzahl der Schlüssel weil `keys()` eine Liste erstellt, in CPython 3 vermute ich stark O(1) weil `keys()` dort eine Objekt erstellt das eine Art `set`-Ansicht der Schlüssel ist und dabei nur eine Referenz auf die Daten des Wörterbuchs enthält. Aber vielleicht meintest Du ja *eigentlich* auch `list(reversed(dict.keys()))`…
Eine Liste zu erstellen ist O(n). Sortieren eine hat untere Schranke, die man wenn man den Begriff Komplexitaet kennt ebenfalls kennen sollte. Und bei zwei Algorithmen die hintereinander ausgefuehrt werden dominiert der komplexere. Damit ist die Frage doch beantwortet, oder?
@Vega:
Die Komplexität von `sorted(dict.keys())` hängt von der Implementation ab. Da das nicht spezifiziert ist, könnte eine Implementation theoretisch einen Monte Carlo Algorithmus für die Sortierung nutzen
Heisst - schau im Code Deiner Implementation nach.
Die Komplexität von `sorted(dict.keys())` hängt von der Implementation ab. Da das nicht spezifiziert ist, könnte eine Implementation theoretisch einen Monte Carlo Algorithmus für die Sortierung nutzen
Heisst - schau im Code Deiner Implementation nach.