Zeitkomplexität von Operationen auf eingebauten Typen

Diese Seite dokumentiert die Zeitkomplexität verschiedener Operationen auf eingebauten Typen in CPython. Andere Python-Implementierungen können ein anderes Laufzeitverhalten haben. Außerdem setzen die angegebenen Kosten genau diese eingebauten Typen voraus, denn Instanzen von Unterklassen können andere Kosten haben.

Wir verwenden die Big O notation, um zu beschreiben, wie die Laufzeit einer Operation mit der Größe ihrer Eingaben wächst. Sofern nicht anders angegeben, bezeichnet n die Anzahl der Elemente, die der Container gerade enthält, und k ist der Wert eines numerischen Parameters, etwa eines Index oder einer Wiederholungszahl.

list

Listen sind veränderbare Sequenzen. Mehr zur Umsetzung findest du unter Wie sind Listen in CPython umgesetzt?. Die größten Kosten entstehen, wenn eine Liste über die aktuell belegte Größe hinauswächst (weil dann alles umziehen muss), oder wenn irgendwo nahe am Anfang eingefügt oder gelöscht wird (weil dann alles dahinter umziehen muss). Musst du an beiden Enden hinzufügen oder entfernen, nimm stattdessen eine collections.deque in Erwägung.

Operation

Komplexität

Kopieren (l.copy())

O(n)

Anhängen (l.append(x)) [1]

O(1)

Entnehmen (l.pop(k)) [1] [2]

O(n - k)

Einfügen (l.insert(k, x)) [1] [2]

O(n - k)

Element lesen (l[k])

O(1)

Element setzen (l[k] = x)

O(1)

Element löschen (del l[k]) [2]

O(n - k)

Iteration

O(n)

Slice lesen (l[i:j])

O(j - i)

Slice setzen (l[i:j] = t) [1]

O(j - i), falls len(t) == j - i, sonst O(n - i + len(t))

Slice löschen (del l[i:j])

O(n - i)

Erweitern (l.extend(t)) [1] [3]

O(len(t))

Sortieren (l.sort()) [4]

O(n log n)

Verketten (l1 + l2)

O(len(l1) + len(l2))

Vervielfachen (l * k)

O(nk)

x in l

O(n)

min(l), max(l)

O(n)

Länge ermitteln (len(l)) [5]

O(1)

tuple

Ein tuple ist eine unveränderliche Sequenz. Weil sich ein Tupel niemals ändern kann, entstehen keine Kosten für Einfügen oder Löschen, und eine Kopie gibt einfach dasselbe Objekt zurück, braucht also konstante Zeit (O(1)).

Operation

Komplexität

Kopieren (tuple(t))

O(1)

Element lesen (t[k])

O(1)

Slice lesen (t[i:j])

O(j - i)

Verketten (t1 + t2)

O(len(t1) + len(t2))

Vervielfachen (t * k)

O(nk)

Iteration

O(n)

x in t

O(n)

min(t), max(t)

O(n)

Länge ermitteln (len(t)) [5]

O(1)

dict, frozendict

Die für dict-Objekte angegebenen Zeiten sind Zeiten für den durchschnittlichen Fall, denn sie setzen voraus, dass die Hashfunktion der Objekte robust genug ist, um Kollisionen selten zu machen. Sie setzen außerdem voraus, dass die Schlüssel gut über die Menge der möglichen Schlüssel verteilt sind. Im schlechtesten Fall, wenn jeder Schlüssel auf denselben Wert hasht, braucht jede der unten mit O(1) angegebenen Operationen stattdessen O(n) Zeit. Sie setzen ferner voraus, dass Hashen und Vergleichen eines Schlüssels O(1) ist. Mehr zur Umsetzung findest du unter Wie sind Dictionarys in CPython umgesetzt?.

Ein frozendict ist unveränderlich, unterstützt also kein Setzen, Löschen oder Aktualisieren von Elementen. Die übrigen Operationen unten gelten für es mit denselben Kosten.

Operation

Komplexität

key in d

O(1)

Kopieren (d.copy()) [6] [7]

O(n)

Element lesen (d[key], d.get(key))

O(1)

Element setzen (d[key] = value) [1]

O(1)

Element löschen (del d[key], d.pop(key))

O(1)

Aktualisieren (d.update(t), d |= t) [1] [3] [7]

O(len(t))

Iteration [7]

O(n)

Länge ermitteln (len(d)) [5]

O(1)

set, frozenset

Siehe dict, denn die Umsetzungen von set und frozenset sind ähnlich, und es gelten dieselben Einschränkungen. Im schlechtesten Fall brauchen die mit O(1) angegebenen Operationen stattdessen O(n) Zeit, und Operationen, die jedes Element nachschlagen, verschlechtern sich entsprechend.

Ein frozenset ist unveränderlich, unterstützt also weder Hinzufügen und Verwerfen noch die Operationen, die an Ort und Stelle aktualisieren. Die übrigen unten gelten für es mit denselben Kosten.

Operation

Komplexität

x in s

O(1)

Kopieren (s.copy()) [6] [7]

O(n)

Hinzufügen (s.add(x)) [1]

O(1)

Verwerfen (s.discard(x), s.remove(x))

O(1)

Vereinigung (s1 | s2, s1.union(s2)) [7]

O(len(s1) + len(s2))

Aktualisieren (s1 |= s2, s1.update(s2)) [1] [7]

O(len(s2))

Schnittmenge (s1 & s2, s1.intersection(s2)) [7] [8]

O(min(len(s1), len(s2)))

Schnittmenge aktualisieren (s1 &= s2, s1.intersection_update(s2)) [1] [7] [8]

O(min(len(s1), len(s2)))

Differenz (s1 - s2, s1.difference(s2)) [7] [9]

O(len(s1))

Differenz aktualisieren (s1 -= s2, s1.difference_update(s2)) [1] [7] [8]

O(min(len(s1), len(s2)))

Symmetrische Differenz (s1 ^ s2, s1.symmetric_difference(s2)) [7]

O(len(s1) + len(s2))

Symmetrische Differenz aktualisieren (s1 ^= s2, s1.symmetric_difference_update(s2)) [1] [7]

O(len(s2))

Länge ermitteln (len(s)) [5]

O(1)

str, bytes, bytearray

str- und bytes-Objekte sind unveränderliche Sequenzen von Zeichen beziehungsweise Bytes. Wie bei Tupeln gibt eine Kopie das ursprüngliche Objekt zurück. Ein bytearray ist veränderbar und unterstützt zusätzlich die verändernden Operationen von list (außer sort()), mit denselben Kosten. Allerdings rückt das Löschen am Anfang mit del (del b[0], del b[:k]) nur den Anfang des Puffers vor, statt die übrigen Bytes zu verschieben, und ist amortisiert O(1).

Operation

Komplexität

Element lesen (s[k])

O(1)

Slice lesen (s[i:j])

O(j - i)

Verketten (s + t) [10]

O(len(s) + len(t))

Vervielfachen (s * k)

O(nk)

Teilzeichenkette suchen (x in s, s.find(x), s.index(x)) [11]

O(n)

Teilzeichenkette rückwärts suchen (s.rfind(x), s.rindex(x)) [11] [12]

O(n × len(x))

Kodieren oder Dekodieren [13]

O(n)

Iteration

O(n)

Länge ermitteln (len(s)) [5]

O(1)

memoryview

memoryview-Objekte erlauben Python-Code, auf die internen Daten eines Objekts zuzugreifen, das das Puffer-Protokoll unterstützt, ohne zu kopieren. Insbesondere gibt das Slicing einer Speicheransicht eine neue Ansicht auf denselben Puffer zurück.

Operation

Komplexität

Erzeugen (memoryview(obj))

O(1)

Element lesen (v[k])

O(1)

Slice lesen (v[i:j])

O(1)

Index (v.index(x)) [11] [14]

O(n)

Zählen (v.count(x)) [14]

O(n)

In Bytes umwandeln (v.tobytes(), bytes(v))

O(n)

Länge ermitteln (len(v)) [5]

O(1)

range

Ein range-Objekt berechnet seine Elemente bei Bedarf aus seinen Werten start, stop und step. Die meisten Operationen hängen daher nicht von der Länge des Bereichs ab.

Operation

Komplexität

Element lesen (r[k])

O(1)

Slice lesen (r[i:j])

O(1)

x in r [15]

O(1)

Index und Anzahl (r.index(x), r.count(x)) [15]

O(1)

Iteration

O(n)

min(r), max(r)

O(n)

Länge ermitteln (len(r)) [5]

O(1)

Anmerkungen