Was ist die Laufzeit für das Einfügen eines Elements in einen Index der arrayList?

Question

Ich frage mich, was ist die Laufzeit für add(index,E) Methode von Java ArrayList. Laut der javadoc amortisiert sich die Laufzeit für den Add-Vorgang O(1). Aber in der Beschreibung von add(index,E) heißt das.

Fügt das angegebene Element an der angegebenen Position in dieser Liste ein. Verschiebt das Element, das sich momentan an dieser Position befindet (falls vorhanden) und alle nachfolgenden Elemente nach rechts (addiert eins zu ihren Indizes).

So sieht es aus wie O(N). Ich fragte mich, wofür wir handeln müssten, wenn die Laufzeit für diesen Vorgang O(1) wäre. Gibt es irgendwelche Amortisationsarbeiten, die durchgeführt werden können, um diese Operation O(1) durchzuführen und die Laufzeit für eine andere Operation zu opfern?

Ich lese, dass Java ArrayList von Arrays unterstützt wird, würde die Datenstruktur Hilfe ändern?

Answer 1

ArrayList hat O (n) Zeit Komplexität für beliebige Indizes hinzufügen/entfernen, aber O (1) für die Operation am Ende der Liste. Closer zu O (1) Nachschlagen impliziert kann etwas sein wie eine Hash Table Datenstruktur mit Index als Schlüssel und Element als Wert gesichert. Die erneute Einfügung dauert O (n) Zeit, da es eine Größenänderung auslöst.

Answer 2

Eine naive Implementierung einer Array-unterstützten Liste würde jedes Objekt, das auf einem Insert verschoben werden soll, als separate Operation kopieren. Glücklicherweise sind die zu verschiebenden Bytes alle zusammenhängend im Speicher und jedes Betriebssystem bietet Unterstützung für das effiziente Kopieren großer Speicherbereiche in einer einzigen, schnellen Operation.

Das Einfügen in die Mitte eines Arrays ist also nicht so schlimm, wie Sie vielleicht denken. Natürlich könnte sich die Änderung der Datenstruktur zu einer verketteten Liste als schneller erweisen, wenn Ihre Anwendung das richtige Zugriffsmuster hat.