Tidskompleksiteten af ​​`indsæt '-operationen i en vektor afhænger af hvor Du indsætter elementet.

Her er en sammenbrud:

* Indsættelse i slutningen (ved hjælp af `push_back` eller tilsvarende): Dette er generelt O (1) - Amortiseret konstant tid . "Amortiseret" betyder, at selvom vektoren lejlighedsvis skal omfordele sin underliggende hukommelse (som tager O (n) tid), er det meste af tiden, at indsættelsen simpelthen placerer elementet i det næste tilgængelige slot. Over mange indsættelser er den gennemsnitlige tid tæt på konstant.

* Indsættelse i en bestemt position (ved hjælp af `indsæt (iteratorposition, værdi)` eller tilsvarende): Dette er o (n) - lineær tid . Her er hvorfor:

1. Find stillingen: Hvis iteratoren gives direkte, er det normalt O (1) at finde positionen inden for den eksisterende vektor. Hvis du imidlertid skal * søge * efter indsættelsespunktet (f.eks. Indsættelse i en sorteret rækkefølge), kan søgetid i sig selv være O (n) eller O (log n) afhængigt af den anvendte søgealgoritme (henholdsvis lineær søgning eller binær søgning). Men den skiftende del dominerer.

2. skiftende elementer: For at gøre plads til det nye element skal alle elementer * efter * indsættelsespunktet forskydes en position til højre. I værste tilfælde (indsættelse i begyndelsen) skal du skifte `n` elementer. I det gennemsnitlige tilfælde (indsættelse i midten) skifter du omtrent `n/2` elementer. I begge tilfælde bidrager den skiftende operation O (n) tidskompleksitet.

Sammendragstabel:

| Indsættelsesplacering | Tidskompleksitet | Forklaring |

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

| Slut (push_back) | O (1) (amortiseret) | Normalt konstant tid. Der kan lejlighedsvis være nødvendigt med omfordeling, men over mange indsættelser forbliver den gennemsnitlige tid tæt på konstant. |

| Specifik position | O (n) | Kræver at skifte alle elementer efter indsættelsespunktet. Den skiftende operation dominerer tidskompleksiteten. Bemærk:Hvis indsættelsespunktet skal findes ved at søge inden for vektoren, vil denne søgningstid blive føjet til den samlede kompleksitet. |

Vigtige overvejelser:

* omfordeling: Når en vektor løber tør for kapacitet, skal den omfordele en større hukommelsesblok og kopiere alle de eksisterende elementer til den nye blok. Denne omfordelingsoperation er O (n). Imidlertid fordobler vektorer ofte deres kapacitet, hver gang de omfatter, hvilket gør omfordeling sjældent nok til, at omkostningerne afskrives over mange indsættelser.

* Vektorimplementering: Specifikationerne ved vektorimplementeringer kan lidt påvirke ydeevnen. For eksempel kan nogle implementeringer muligvis bruge mere sofistikerede hukommelsesstyringsteknikker.

Eksempel (C ++):

`` CPP

#include

#include

int main () {

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

// Indsættelse i slutningen (amortiseret o (1))

myvector.push_back (6);

std ::cout <<"Efter push_back:";

for (int x:myVector) std ::cout < std ::cout <

// Indsættelse i en bestemt position (O (n))

myvector.insert (myvector.begin () + 2, 10); // Indsæt 10 ved indeks 2

std ::cout <<"Efter indsættelse:";

for (int x:myVector) std ::cout < std ::cout <

return 0;

}

`` `

I sammendraget skal du være opmærksom på * hvor * du indsætter i en vektor. `Push_back` er din ven, hvis du bare har brug for at tilføje til slutningen. Hvis du har brug for at indsætte i midten, skal du overveje præstationsimplikationerne, især hvis du laver mange sådanne indsættelser. Hvis der kræves hyppige midterste indsættelser, kan alternative datastrukturer som tilknyttede lister eller afbalancerede træer være mere egnede.