Die zeitliche Komplexität des `Insert` -Betriebs in einem Vektor hängt von ab, wobei Sie fügen das Element ein.

Hier ist eine Aufschlüsselung:

* Einfügen am Ende (mit `push_back` oder äquivalent): Dies ist im Allgemeinen o (1) - amortisierte konstante Zeit . "Amortisiert" bedeutet, dass der Vektor gelegentlich seine zugrunde liegende Erinnerung (die o (n) Zeit in Anspruch nimmt) neu zuordnen muss, aber die meiste Zeit die Einfügung legt einfach das Element in den nächsten verfügbaren Steckplatz ein. Über viele Einfügungen liegt die durchschnittliche Zeit nahezu konstant.

* Einfügen an einer bestimmten Position (mit `Insert (Iteratorposition, Wert) oder gleichwertig): Dies ist o (n) - lineare Zeit . Hier ist der Grund:

1. Die Position finden: Wenn der Iterator direkt verabreicht wird, ist die Position der Position innerhalb des vorhandenen Vektors normalerweise o (1). Wenn Sie jedoch nach dem Insertionspunkt suchen müssen (z. B. in einer sortierten Reihenfolge), kann die Suchzeit selbst abhängig vom verwendeten Suchalgorithmus (lineare Suche bzw. binäre Suche) o (n) oder o (log n) sein. Aber der sich verändernde Teil dominiert.

2. Elemente verschieben: Um Platz für das neue Element zu schaffen, müssen alle Elemente * nach * der Einfügenpunkt eine Position nach rechts verschoben werden. Im schlimmsten Fall (Einfügen am Anfang) müssen Sie die Elemente verändern. In dem durchschnittlichen Fall (Einfügen in die Mitte) verschieben Sie ungefähr N/2` -Elemente. In beiden Fällen trägt der Schaltvorgang o (n) bei Zeitkomplexität.

Zusammenfassungstabelle:

| Einfügungsort | Zeitkomplexität | Erläuterung |

| ---------------------- | -------------------

| End (push_back) | O (1) (amortisiert) | Normalerweise konstante Zeit. Eine Neuzuweisung kann gelegentlich erforderlich sein, aber über viele Einfügungen bleibt die durchschnittliche Zeit nahezu konstant. |

| Spezifische Position | O (n) | Erfordert das Verschieben aller Elemente nach dem Einfügen. Der Verlagerungsvorgang dominiert die zeitliche Komplexität. Hinweis:Wenn der Insertionspunkt durch die Suche innerhalb des Vektors gefunden werden muss, würde diese Suchzeit zur Gesamtkomplexität hinzugefügt. |

Wichtige Überlegungen:

* Neuvergleich: Wenn ein Vektor aus der Kapazität ausgeht, muss er einen größeren Speicherblock neu zuordnen und alle vorhandenen Elemente in den neuen Block kopieren. Diese Neuzuweisung -Operation ist O (n). Die Vektoren verdoppeln jedoch ihre Kapazität jedoch jedes Mal, wenn sie neu zuordnen, so dass die Neuzuweisung selten genug macht, dass die Kosten über viele Einfügungen abgeschrieben werden.

* Vektorimplementierung: Die Einzelheiten der Vektorimplementierungen können die Leistung leicht beeinflussen. Beispielsweise könnten einige Implementierungen komplexere Gedächtnisverwaltungstechniken verwenden.

Beispiel (C ++):

`` `cpp

#include

#include

int main () {

std ::vector myVector ={1, 2, 3, 4, 5};

// am Ende einfügen (amortisiert O (1))

myVector.push_back (6);

std ::cout <<"After Push_back:";

für (int x:myVector) std ::cout < std ::cout <

// Einfügen an einer bestimmten Position (o (n))

myVector.insert (myVector.begin () + 2, 10); // 10 bei Index 2 einfügen

std ::cout <<"Nach dem Einfügen:";

für (int x:myVector) std ::cout < std ::cout <

Rückkehr 0;

}

`` `

Zusammenfassend achten Sie auf *, wo Sie * in einen Vektor einfügen. `push_back` ist dein Freund, wenn du nur zum Ende hinzufügen musst. Wenn Sie in die Mitte einfügen müssen, berücksichtigen Sie die Auswirkungen auf die Leistung, insbesondere wenn Sie viele solcher Einfügungen durchführen. Wenn häufige mittlere Insertionen erforderlich sind, sind alternative Datenstrukturen wie verknüpfte Listen oder ausgewogene Bäume möglicherweise besser geeignet.