Ich frage mich, was ist die Zeit Komplexität der Pop-Methode der Liste Objekte in Python (in CPython insbesondere). Beeinflusst auch der Wert von N für list.pop (N) die Komplexität?Wie hoch ist die zeitliche Komplexität von Popup-Elementen in Python?
Pop() für das letzte Element sollte O (1) sein, da Sie nur das Element zurückgeben müssen, auf das vom letzten Element im Array verwiesen wird, und den Index des letzten Elements aktualisieren. Ich würde erwarten, dass pop() für ein beliebiges Element O (N) ist und im Durchschnitt N/2 Operationen erfordert, da Sie alle Elemente über das Element hinaus verschieben müssen, das Sie eine Position im Zeiger-Array entfernen.
Ja, es ist O (1) das letzte Elements einer Python Liste Pop, und O (N), um ein willkürliches Element Pop (da der ganze Rest der Liste verschoben werden muss).
Hier ist ein großer Artikel darüber, wie Python-Listen gespeichert und manipuliert: http://effbot.org/zone/python-list.htm
Also nur um es klar zu machen, list.pop (0) ist O (n) und list.pop() ist O (1). –
Und um beide Operationen in O (1) zu bekommen, benutze collections.deque siehe [hier] (https://wiki.python.org/moin/TimeComplexity) – galath
Die kurze Antwort hier ist: https://wiki.python.org/moin/TimeComplexity
Ohne Argumente seiner O Pop (1)
Mit einem Argument Pop:
Durchschnittliche Zeitkomplexität:
Jedes Mal, wenn Sie in einem setzen Wert die Zeit Komplexität dieser Operation ist O (n - k).
Zum Beispiel, wenn Sie eine Liste der Artikel 9 als vom Ende der Liste zu entfernen, ist 9 Operationen und von Anfang Entfernen der Liste 1 Operationen ist (die 0-te Index zu löschen und alle andere bewegliche Elemente zu ihrem aktuellen Index - 1)
Da n - k für das mittlere Element einer Liste k Operationen ist, kann der Durchschnitt auf O (k) verkürzt werden.
Eine andere Möglichkeit, darüber nachzudenken, ist, dass jeder Index einmal aus Ihrer 9-Item-Liste entfernt wurde. Das wären insgesamt 45 Operationen. (9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45)
45 ist gleich O (nk) und da die Pop-Operation O (n) aufgetreten ist, teilen Sie nk durch n erhalten O (k)
Amortisierte Worst Case Zeitkomplexität
Stellen Sie sich wieder eine Liste der Artikel 9 haben.Stellen Sie sich vor, Sie entfernen alle Elemente der Liste und der schlimmste Fall tritt auf, und Sie entfernen jedes Mal das erste Element der Liste.
Da die Liste schrumpft um 1 jedesmal, wenn die Anzahl der gesamten Operationen jedesmal nimmt von 9 bis 1.
9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45 45 entspricht O (nk). Da Sie 9 Operationen durchgeführt haben und 9 O (n) ist, um das amortisierte Worst-Case-Szenario zu berechnen, machen Sie O (nk)/O (n), was 0 (0)
angibt und amortisierte Worst-Case-Zeit Komplexität ist auch eine Art von richtig. Beachten Sie, dass O (k) etwa O (1/2n) und die Konstante fallen gleich O (n)
Worst Case Zeitkomplexität
Ich bin mit der Antwort gegeben, aber die Erklärung ist imho falsch. Sie können jedes Objekt zu einer O (1) Zeit aus einer Liste entfernen (im Wesentlichen den vorherigen Zeiger auf den nächsten Punkt setzen und diesen entfernen). Das Problem besteht darin, dass Sie das Verzeichnis an dieser Stelle durchqueren müssen, um das Objekt zu finden Punkt (dauert O (N) Zeit, keine Mittelung erforderlich.) Zum Schluss noch ein Sonderfall :, pop (0) braucht O (1), nicht O (0). – ntg
@ntg die Liste ist ein Array von Zeigern. Um einen Zeiger aus dem Array in der Mitte zu entfernen, müssen alle nachfolgenden Zeiger im Array nach oben verschoben werden, wobei die Zeit proportional zur Größe der Liste (die wir mit N bezeichnen) proportional ist, also O (N) ist. . Um das N in der Big-O-Notation zu verdeutlichen, ist NICHT der Index des Elements, das zurückgegeben wird, sondern eine Funktion, die die Laufzeit des Algorithmus mit O (1) zeitlich begrenzt - dh sie hängt nicht von der Größe von Die Liste. O (N) bedeutet, dass die Begrenzungsfunktion eine Konstante mal der Größe der Liste ist, f (n) = c * n + b. – tvanfosson
Ich stehe korrigiert :) In der Tat ist die Liste Implementierung ein Array von Zeigern. Deine Antwort ist also richtig. Mit pop (N) in Ihrer Antwort meinen Sie pop (k), N wobei k die Position des zu entfernenden Elements ist und die Größe des Arrays N ist. Dann kann k von 0 bis N-1 reichen, also pro Durchschnitt N/2 Operationen zum Verschieben der Elemente k + 1, ...., N-1 um eine Position nach hinten. – ntg