Das deutsche Python-Forum

Hallo,

Kann mir jemand sagen, welcher Komplexitäts-Klasse die Funktionen:
sorted(dict.keys()) und reversed(dict.keys)
angehören?

Na, Hausaufgaben zu machen?

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()))`…

@BlackJack Ja, ich meinte reversed(dict.keys()) und wie sieht es mit sorted(dict.keys()) aus?

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.

Okay, hab's verstanden, Danke.