Warum ist das einfügen am Ende eines dynamischen Arrays O(1) beim einlegen in der Mitte ist O(n)?

Question

Entsprechend dem Wikipedia-Artikel über dynamische arrays, einfügen/löschen am Ende des Arrays ist O(1) einfügen/löschen Mitte O(n).Warum genau ist das?

Auch wenn ich ein dynamisches array mit 5 Elementen und füge ich ein neues element an position 6 der operation ist O(n) in der Erwägung, dass, wenn ich die Funktion zum Anhängen an das Ende des Arrays ist es O(1).Das ist nicht der gleiche Betrieb vorausgesetzt, das array muss nicht die Größe, die in jedem Fall?Oder ist das Anhängen des dynamischen Arrays wirklich setzen Sie das neue element irgendwo neben position 6?

Vielen Dank!

EDIT: Ich denke, dass meine wichtigsten Verwirrung ist der Unterschied zwischen dem einfügen am Ende des Arrays und das einfügen an einer bestimmten position das entspricht dem Ende des Arrays.

Ich nehme an, ein Zeiger auf die Speicheradresse am Ende des Arrays gehalten wird praktisch und das ist, warum Sie die append-operation ist schnell.Umgekehrt, wenn ich geben Sie eine genaue position (auch wenn es das Ende des Arrays), die es nicht wissen, dass das einfügen an dieser position ist gleichbedeutend mit dem oben genannten Speicher-Adresse an, damit es Durchlaufen muss das gesamte array, eh?

Answer 1

die Größenordnung würde eigentlich die „dynamische Array“ vollständig auf, welche Art von Datenstruktur abhängig ist ( „dynamic array“ ist keine streng Datenstruktur definiert, dann ist es eher ein gewünschtes Ergebnis erreicht, indem eine bestimmte Datenstruktur verwendet ). Das Beispiel, das Sie geben würde, dass durch die Verwendung einer verketteten Liste erreicht durch ein dynamisches Array reflektieren sein. Zusätzlich zu dem Ende könnte O (1), wenn die Listenstruktur einen Zeiger auf das letzte Element gehalten. Einfügen (unabhängig vom Index) erfordern würde, die verknüpfte Liste durchlaufen, dh eine Operation pro Knoten bis zu dem gewünschten Index.

Answer 2

Um am Ende eines Arrays einsetzen, müssen Sie einfach dort den Punkt bringen.

in der Mitte eines Feldes einzufügen, müssen Sie die Einzelteile nach diesem Punkt nach dem anderen bewegen.

vom Ende eines Arrays löschen, die Sie gerade von einem seiner Zählung fallen.

So löschen Sie von der Mitte Sie tun müssen, dass und verschiebt die anderen Elemente nach unten.

Es ist die Verschiebung , die es in O schaltet (n).

Answer 3

Es ist ziemlich einfach:

in der Mitte einsetzen beinhaltet jedes später Element bewegt über von 1. So fügen Sie am Ende, wenn es zusätzlichen Platz reserviert ist, wird das Element nur dort gespeichert, aber wenn keine neuen Raum zugeordnet ist. Damit dieser Vorgang wird in konstante Zeit abgeschrieben.

Answer 4

Zusätzlich zu Adam Robinson ausgezeichneter Zusammenfassung: Dies ist nicht nur Theorie. Ich habe eine beliebige Anzahl von Situationen, in denen ein dynamisches Array von wiederholt bis zum Ende des Arrays angehängt aufgebaut gesehen. Dies funktioniert auf o(N**2) Leistung aus, da das Array wiederholt werden neu zugeordnet muss, zwingt jedes ihrer Mitglieder in die neue Matrixstruktur kopiert werden. Die Umschichtungen passieren können, auf nur ein Zehntel der append-Operationen, aber das ist schon schlimm genug, und ist immer noch o(N**2) Performance-weise.

In STL kann diese Leistungseinbuße durch den Aufruf vector::reserve(N) vermieden werden, bevor sie in den Vektor zu schreiben; aber dieser Schritt wird oft übersehen.

Answer 5

Tatsächlich, es ist nicht Groß-aber O Big-Theta.