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

Question

Entsprechend dem Wikipedia-Artikel auf dynamic arrays, Einfügen/Löschen am Ende des Arrays ist O (1) beim Einfügen/Löschen von der Mitte ist O (n). Warum genau ist das?

Auch - wenn ich ein dynamisches Array mit 5 Elementen habe und ein neues Element an Position 6 einfügen, ist die Operation O (n), wenn ich die Funktion an das Ende des Arrays angehängt habe, ist O (1). Ist dies nicht dieselbe Operation, wenn das Array nicht in beiden Fällen neu skaliert werden muss? Oder fügt das Anfügen an das dynamische Array das neue Element wirklich neben Position 6 ein?

Danke!

EDIT: Ich denke, meine Haupt Verwirrung ist der Unterschied zwischen dem Einfügen am Ende des Arrays und Einfügen an einer bestimmten Position, die dem Ende des Arrays entspricht.

Ich nehme an, ein Zeiger auf die Speicheradresse des Endes des Arrays wird griffbereit gehalten, und deshalb ist die Append-Operation schnell. Umgekehrt, wenn ich eine genaue Position (selbst wenn es das Ende des Arrays ist) angeben, wird es nicht wissen, dass das Einfügen an dieser Position ist gleichbedeutend mit der oben genannten Speicheradresse, so dass es das gesamte Array durchlaufen muss, wie?

Answer 1

Die Größenordnung würde vollständig davon abhängen, welche Art von Datenstruktur das "dynamische Array" tatsächlich ist ("dynamisches Array" ist keine streng definierte Datenstruktur, es ist eher ein erwünschtes Ergebnis, das durch die Verwendung bestimmter Daten erreicht wird) Struktur). Das Beispiel, das Sie angeben, wäre ein dynamisches Array, das durch Verwendung einer verketteten Liste erreicht wird. Das Hinzufügen zum Ende könnte O (1) sein, wenn die Listenstruktur einen Zeiger auf das letzte Element hält. Das Einfügen (unabhängig vom Index) würde das Durchlaufen der verknüpften Liste erfordern, was eine Operation pro Knoten bis zum gewünschten Index bedeutet.

Answer 2

Um am Ende eines Arrays einzufügen, müssen Sie das Element einfach dort platzieren.

Um in die Mitte eines Arrays einzufügen, müssen Sie die Elemente nach diesem Punkt um eins nach oben verschieben.

Um am Ende eines Arrays zu löschen, löschen Sie einfach seine Zählung um eins.

Um aus der Mitte zu löschen, müssen Sie und die anderen Elemente nach unten verschieben.

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

Answer 3

Es ist ziemlich einfach:

in der Mitte einsetzen beinhaltet jedes später Element bewegt über von 1. am Ende einzufügen, wenn es zusätzlichen Platz reserviert ist, wird das Element nur dort gespeichert, aber wenn nicht neu Platz ist zugewiesen. Somit wird diese Operation in durchgeführt.

Answer 4

Eigentlich ist es nicht Big-O, sondern Big-Theta.

Answer 5

Zu Adam Robinsons ausgezeichneter Zusammenfassung hinzufügen: Dies ist nicht nur Theorie. Ich habe eine beliebige Anzahl von Situationen gesehen, in denen ein dynamisches Array erstellt wurde, indem wiederholt an das Ende des Arrays angehängt wurde. Dies funktioniert auf Grund der Tatsache, dass das Array wiederholt neu zugewiesen werden muss, wobei jedes seiner Mitglieder gezwungen wird, in die neue Array-Struktur kopiert zu werden. Die Neuzuweisungen können nur bei 1/10 der Append-Operationen passieren, aber das ist schlimm genug und ist immer noch leistungsmäßig.

In STL kann diese Leistungseinbuße vermieden werden, indem vector::reserve(N) vor dem Schreiben in den Vektor aufgerufen wird; aber dieser Schritt wird oft übersehen.