Was ist die zeitliche Komplexität von zip() in Python?

Question

Wie kann ich die zeitliche Komplexität von zip() berechnen?

testList = [[1,2,3]for _ in range(5)] 
    zip(*testList) 

Answer 1

Angenommen, Sie zip N iterables.

In Python 3.x, die Zip-Funktion selbst läuft in O(1) Zeit, da es ordnet nur eine spezielle iterable (das zip-Objekt bezeichnet), und weist das Parameterfeld zu einem internen Bereich. Der Funktionsaufruf selbst (bevor die Steuerung in zip ankommt) ist O(N), da der Interpreter die Parameter in ein Array konvertieren muss. Jeder nachfolgende next Aufruf auf dem Iterator läuft auch in O(N). Das Zip-Objekt erschöpft sich daher in O(N*M) unter der Annahme, dass M die durchschnittliche (oder minimale) Länge der Iterablen ist, mit Ausnahme der Zeit, die die Iterablen selbst benötigen, um Items zu generieren (wie es unabhängig von zip ist). In Python 2.x gibt die ZIP-Funktion eine Liste zurück. Diese Liste muss während des Aufrufs erstellt werden, dh sie entspricht dem Iterator im vorherigen Beispiel, also O(N*M), wobei die in den gezippten Iterablen verbrachte Zeit nicht berücksichtigt wird.