Was ist die Kosten/ Komplexität von insert-Liste an einem bestimmten Ort?

In Python, ein Liste hat list.insert(i, x) auf "Einfügen eines Elements an einer bestimmten position.". In C++ gibt es eine Liste als gut. In C++, Kosten/Komplexität von einfügen eines element an einer beliebigen Stelle ist O(1). Es ist das gleiche für eine Python-Liste? Wenn nicht, kann alles andere werden verwendet, um O(1) legen Sie die Zeit in Python?

InformationsquelleAutor user3654650 | 2014-11-22
  1. 16

    Python-Sprache ist nicht angegeben, die Umsetzung dieser Maßnahmen, so dass unterschiedliche Implementierungen können unterschiedliche Verhalten. Für CPython, die Komplexität der list.insert ist O(n), wie gezeigt, auf dieses nützliche wiki-Seite. Ich bin mir nicht bewusst keine Liste-wie Struktur geben O(1) Erfüllungsort für einfügen an beliebiger index. (Ein dict liefert O(1) einfügen der Leistung in der durchschnittlichen Fall, aber ist nicht bestellt und nicht die Durchsetzung einer zusammenhängenden Sequenz von Indizes.) Die blist Bibliothek bietet eine optimierte Liste Typ, der hat einen O(log n) einfügen.

    InformationsquelleAutor BrenBarn
  2. 14

    Liste

    Den Durchschnittlichen Fall übernimmt die Parameter generiert, die gleichmäßig nach dem Zufallsprinzip.

    Intern eine Liste wird dargestellt als ein array zu verwenden; die größten Kosten kommen, vom Anbau über die aktuelle Allokation der Größe (weil alles muss sich bewegen), oder das einfügen oder löschen irgendwo am Anfang (weil alles nach, die sich bewegen müssen). Wenn Sie brauchen, um hinzuzufügen/entfernen Sie an beiden enden, verwenden Sie ein Sammlungen.deque statt.

    Was ist die Kosten/Komplexität von insert-Liste an einem bestimmten Ort?

    So einfügen eines Elements an der angegebenen position wird immer die Zeit, die Komplexität der O(n) als beide einfügen Methode und schneiden Zeit hat die Komplexität der O(n) und O(k).
    Nur Anhängen die Einsätze am Ende der Liste haben O(1) Zeit Komplexität.
    Von Python Wiki

    Lists:
                               Complexity
Operation     | Example      | Class         | Notes
--------------+--------------+---------------+-------------------------------
Index         | l[i]         | O(1)          |
Store         | l[i] = 0     | O(1)          |
Length        | len(l)       | O(1)          |
Append        | l.append(5)  | O(1)          |
Clear         | l.clear()    | O(1)          | similar to l = []

Slice         | l[a:b]       | O(b-a)        | l[1:5]:O(l)/l[:]:O(len(l)-0)=O(N)
Extend        | l.extend(...)| O(len(...))   | depends only on len of extension
Construction  | list(...)    | len(...)      | depends on lenghth of argument

check ==, !=  | l1 == l2     | O(N)          |
Insert        | l[a:b] = ... | O(N)          |
Delete        | del l[i]     | O(N)          | 
Remove        | l.remove(...)| O(N)          | 
Containment   | x in/not in l| O(N)          | searches list
Copy          | l.copy()     | O(N)          | Same as l[:] which is O(N)
Pop           | l.pop(...)   | O(N)          |
Pop           | l.pop()      | O(1)          | same as l.pop(-1), popping at end
Extreme value | min(l)/max(l)| O(N)          |
Reverse       | l.reverse()  | O(N)          |
Iteration     | for v in l:  | O(N)          |

Sort          | l.sort()     | O(N Log N)    | key/reverse doesn't change this
Multiply      | k*l          | O(k N)        | 5*l is O(N): len(l)*l is O(N**2)

    Vom hier

    InformationsquelleAutor Tanveer Alam
  3. 3

    Nein, es ist nicht die gleiche Komplexität. Laut Python ist die offizielle Zeit Komplexität Seite1, mit list.insert hat immer O(n) (linear) Komplexität.

    Auch eine Python-Liste ist nicht genau das gleiche wie ein C++ - Liste. In der Tat, eine Python-Liste ist mehr vergleichbar mit einer C++ std::vector wenn überhaupt.

    1Gut, CPython ist die offizielle Seite. Ich weiß nicht, über andere Implementierungen wie IronPython oder Jython.

    InformationsquelleAutor iCodez
  4. 0

    Python ist eine Sprache. Mehrere Implementierungen existieren, und Sie können verschiedene Implementierungen für Listen. So, ohne Blick auf den code von einer tatsächlichen Implementierung können Sie nicht sicher wissen, wie die Listen implementiert sind und wie Sie sich Verhalten, unter bestimmten Umständen.

    Meine Wette wäre, dass die Verweise auf die Objekte in einer Liste gespeichert sind, in zusammenhängenden Speicher (sicherlich nicht als eine verknüpfte Liste...). Wenn das wirklich so ist, dann ist das einfügen über x.einfügen bewirkt, dass alle Elemente hinter dem eingefügten element verschoben werden. Diese kann getan werden effizient durch die hardware, sondern die Komplexität wäre immer noch O(n).

    Für die kleinen Listen, die halbieren Vorgang kann mehr Zeit in Anspruch als x ist.einfügen, obwohl die ehemaligen ist O(log n), während die letzteren ist O(n). Für lange Listen, allerdings würde ich raten, dass x.einfügen der Engpass. In solchen Fällen müssen Sie erwägen, eine andere Datenstruktur.

    • Danke. Ich arbeite mit cPython, nicht auf die der anderen Implementierungen. Sie schreiben: "Sie müssen berücksichtigen, dass mit einer anderen Datenstruktur." - was ist besser?
    • Ich denke, Schnellste Datenstruktur zum speichern und abrufen hash-Tabellen.
    InformationsquelleAutor Isuru Madusanka
Schreibe einen Kommentar