webentwicklung-frage-antwort-db.com.de

Warum ist die Lösch- und Einfügeoperation für verknüpfte Listen komplex? O(1) ? sollte es nicht sein von O(n)

Es wird gesagt, dass die Komplexität der LinkedList-Funktion zum Entfernen und Hinzufügen von O(1) ist. und im Fall von ArrayList ist es von O(n)

Berechnung für ArrayList der Größe "M": Wenn ich das Element an der N-ten Position entfernen möchte, kann ich mit dem Index in einem Zug direkt zur N-ten Position wechseln (ich muss nicht bis zum N-ten Index durchlaufen), und dann kann ich entfernen Das Element, bis zu diesem Punkt ist die Komplexität O(1), dann muss ich den Rest der Elemente verschieben (MN verschiebt), so dass meine Komplexität linear ist, dh O (M-N + 1). Daher ist das Löschen oder Einfügen am Ende die beste Leistung (als N ~ M), und das Löschen oder Einfügen am Anfang ist am schlechtesten (als N ~ 1).

Nun die LisnkedList der Größe "M": Da wir das N-te Element in der LinkedList nicht direkt erreichen können, müssen wir N-Elemente durchlaufen, um auf das N-te Element zuzugreifen. Daher ist die Suche in der LinkedList teurer als die ArrayList ... aber Remove und die Add-Operationen werden im Fall von LinkedList als O(1) bezeichnet, da die Shift in LinkedList nicht beteiligt ist, aber es ist eine Queroperation involviert, die mit rechter Hand verbunden ist. Die Komplexität sollte also in der Reihenfolge O(n) liegen, wobei die schlechteste Performance am Endknoten und die beste Performance am Kopfknoten liegt. 

Könnte mir bitte jemand erklären, warum wir beim Berechnen der Komplexität der LinkedList-Entfernungsoperation nicht die Traversenkosten berücksichtigen?

Ich möchte also verstehen, wie es im Java.util-Paket funktioniert. und wenn ich dasselbe in C oder C++ implementieren möchte, wie würde ich das O(1) für zufälliges Löschen und Einfügen in LinkedList erreichen?

6
Aditya Agarwal

Remove und die Add-Operationen werden als O(1) bezeichnet, im Fall von LinkedList, da in LinkedList die Verschiebung nicht beteiligt ist, aber es ist eine Verfahroperation involviert, oder?

Wenn Sie an einem Ende einer verknüpften Liste hinzufügen, ist kein Durchlauf erforderlich, solange Sie auf beide Enden der Liste verweisen. Dies ist, was Java für seine add und addFirst / addLast Methoden macht.

Gleiches gilt für parameterlose remove und removeFirst / removeLast Methoden - sie arbeiten an Listenenden.

remove(int) und remove(Object) Operationen sind dagegen nicht O (1). Sie erfordern eine Durchquerung, sodass Sie ihre Kosten als O (n) richtig angegeben haben.

16
dasblinkenlight

Die Komplexität des Entfernens gilt als gegeben, wenn Sie bereits den Zeiger auf die rechte Position des zu entfernenden Elements haben.

Wird nicht als die Kosten betrachtet, die Sie für die Suche aufgewendet haben

Information on this topic is now available on Wikipedia at: Search data structure

    +----------------------+----------+------------+----------+--------------+
    |                      |  Insert  |   Delete   |  Search  | Space Usage  |
    +----------------------+----------+------------+----------+--------------+
    | Unsorted array       | O(1)     | O(1)       | O(n)     | O(n)         |
    | Value-indexed array  | O(1)     | O(1)       | O(1)     | O(n)         |
    | Sorted array         | O(n)     | O(n)       | O(log n) | O(n)         |
    | Unsorted linked list | O(1)*    | O(1)*      | O(n)     | O(n)         |
    | Sorted linked list   | O(n)*    | O(1)*      | O(n)     | O(n)         |
    | Balanced binary tree | O(log n) | O(log n)   | O(log n) | O(n)         |
    | Heap                 | O(log n) | O(log n)** | O(n)     | O(n)         |
    | Hash table           | O(1)     | O(1)       | O(1)     | O(n)         |
    +----------------------+----------+------------+----------+--------------+

 * The cost to add or delete an element into a known location in the list (i.e. if you have an iterator to the location) is O(1). If you don't know the location, then you need to traverse the list to the location of deletion/insertion, which takes O(n) time. 
** The deletion cost is O(log n) for the minimum or maximum, O(n) for an arbitrary element.
6
Rafael Lima

Ja, Sie sind korrekt, wenn Sie zwei Vorgänge (Indizieren und Einfügen) in einem Arbeitsgang berücksichtigen. In diesem Fall trifft dies nicht zu, da beim Einfügen eines Knotens in die Mitte einer verknüpften Liste davon ausgegangen wird, dass Sie sich bereits an der Adresse befinden, an der Sie den Knoten einfügen müssen.

Die zeitliche Komplexität des Zugriffs auf den Knoten ist O(n), während nur das Einfügen eines Knotens O (1) ist.

Beim Einfügen am Kopf müssen Sie das Element hinzufügen und den Kopfzeiger aktualisieren.

newnode->next = head;
head = newnode;

Beim Einfügen am Ende müssen Sie einen Zeiger auf das Endelement setzen, das Element am Endstück hinzufügen und den Endzeiger aktualisieren.

tail->next = newnode;
tail = newnode;

Um das Kopfelement zu löschen, muss der Kopf aktualisiert und das vorherige Kopfelement gelöscht werden.

temp = head;
head = head->next;
delete temp; /* or free(temp); */

Alle oben genannten Vorgänge sind triviale Operationen und hängen nicht von der Anzahl der Elemente in der verknüpften Liste ab. Daher sind sie O(1)

Das Löschen des Endelements wäre jedoch eine O(n) -Operation, denn obwohl Sie möglicherweise einen Endzeiger haben, benötigen Sie immer noch den vorletzten Knoten, der als neuer Endknoten (durch Aktualisieren) eingerichtet würde den Endzeiger und das nächste Member des Knotens auf NULL setzen). Dazu müssen Sie die gesamte verknüpfte Liste durchlaufen.

penultimate_el = find_penultimate_el(head); /* this is O(n) operation */
delete tail; /* or free(tail) */
tail = penultimate_el;
tail->next = NULL;
1
Ankit Joshi

ArrayList liefert ein veränderbare Array und speichert "Referenzen" oder "Zeiger" auf den tatsächlichen Speicher . Dieses Array von Referenzen muss neu erstellt werden, wenn das Array über seine zugewiesene Größe hinaus erweitert wird. Mit anderen Worten, das Einfügen eines Knotens am Anfang erfordert, dass entweder alle vorhandenen Elemente nach oben verschoben werden oder die gesamte Liste neu zugewiesen wird, wenn sie über die zugewiesene Größe hinausgeht. Deshalb ist das Einfügen O(n).

Eine LinkedList besteht aus einer Kette von Knoten. Jeder Knoten wird getrennt zugewiesen. Beim Einfügen müssen Sie also nicht alle Knoten durchqueren. Und deshalb hat es die Komplexität O(1). Wie auch immer, wenn Sie am Ende einfügen und nur den ersten Knoten referenzieren, müssen Sie möglicherweise die gesamte Liste durchlaufen. In diesem Fall ist die Komplexität O (n) .

EDIT

Wenn Sie sich den Quellcode von Java.util.LinkedList ansehen, können Sie feststellen, dass LinkedList immer die Spur des letzten Elements verfolgt

Nachfolgend einige Codeausschnitte der aktuellen Java.util.LinkedList-Klasse.

package Java.util;

...

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, Java.io.Serializable
{
    transient int size = 0;

    /**
     * Pointer to first node.
     */
    transient Node<E> first;

    /**
     * Pointer to last node.
     */
    transient Node<E> last;


    ...
    ...


    /**
     * Appends the specified element to the end of this list.
     */
    public boolean add(E e) {
        linkLast(e);
        return true;
    }



    ...
    ...


    /**
     * Links e as last element.
     */
    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }


    ...
    ...

}

Siehe insbesondere die linkLast()-Methode. Es wird nicht die gesamte Liste durchlaufen. Das Element wird einfach am Ende der Liste eingefügt. Aus diesem Grund ist die Komplexität der Zeit O(1).

1
Raman Sahasi

Wenn wir die Implementierung aus der Sicht der C-Sprache betrachten, erhalten wir ein klares Verständnis. Während wir Elemente zu einer konstanten Zeit im Array hinzufügen und entfernen können, müssen wir nicht das gesamte Array durchlaufen. Beispiel: Wenn das Array [1,2,3,4] ist, kann die 5 direkt bei Arr [arr. length] postion, in ähnlicher Weise können wir ein Element zu einer konstanten Zeit entfernen. Die zu löschende Position ist Arr [arr.length-1], aber lassen Sie uns ein Szenario sehen, in dem die von Ihnen deklarierte Array-Größe 4 ist und wir dann ein weiteres Element hinzufügen möchten Wir können klar erkennen, dass für die Elemente, die hinzugefügt werden sollen, kein Platz vorhanden ist. Daher müssen wir ein neues Array mit einer Größe erstellen, z. B. das Doppelte des vorherigen Arrays, dh Größe 8. Dann müssen alle Elemente des vorherigen Arrays vorhanden sein Hier kopiert und die neuen Elemente werden an der fünften Position hinzugefügt, dh Arr [arr.length], daher ist die Komplexität der Einfügezeit O(n), da sie direkt proportional zur Anzahl der Elemente des vorherigen Arrays ist hat.

Wenn wir nun zu einer verknüpften Liste kommen, die keine feste Größe hat (sie wird dynamisch im Heap-Speicher zugewiesen), können wir die erste und letzte Position mit dem Kopf- und Endzeiger verfolgen. Unabhängig von der Größe der verknüpften Liste müssen wir also nur den Zeiger von Kopf und ändern tail, wodurch die Zeitkomplexität auf O(1) erhöht wird, um endlich einen neuen Knoten zu erstellen, ändern Sie den Verknüpfungsteil des aktuellen tail in diese neue Knotenadresse und erstellen Sie diesen neuen Knoten als tail.For Beim erstmaligen Einfügen müssen wir einen neuen Knoten erstellen, den Verbindungsteil dieses Knotens als aktuelle Kopfadresse festlegen und diesen neuen Knoten zuletzt als Kopf hinzufügen. Auf diese Weise fügen wir ein Element an der ersten Position hinzu, indem wir nur den einen Knoten ändern. Die Zeitkomplexität ist daher O (1 ).

0
Kunal Hazard