Pythons eingebaute Typen: Die Zeitkomplexität im Überblick

Time complexity of operations on Python's built-in types

Dieses Dokument der offiziellen Python-Dokumentation listet die Zeitkomplexität (Big-O-Notation) aller wichtigen Operationen auf den eingebauten Typen von CPython auf: list, tuple, dict, set, str, bytes, bytearray, memoryview und range. Es zeigt, welche Operationen konstant (O(1)) sind und welche linear (O(n)) oder logarithmisch (O(n log n)) skalieren. Besonders nützlich: Die Hinweise zu Implementierungsdetails, etwa warum das Löschen am Anfang einer Liste teuer ist und wann collections.deque die bessere Wahl ist. Die Angaben gelten für CPython; andere Implementierungen können abweichen.