Tidskomplexiteten för "insatt" -operationen i en vektor beror på
där Du sätter in elementet.
Här är en uppdelning:
* Inserting i slutet (med `push_back` eller motsvarande): Detta är i allmänhet o (1) - amorterad konstant tid . "Amortized" betyder att även om vektorn ibland måste omfördela sitt underliggande minne (som tar o (n) tid), för det mesta placerar infogningen helt enkelt elementet i nästa tillgängliga spår. Under många insättningar är den genomsnittliga tiden nära konstant.
* Inserting i en specifik position (med hjälp av `Insert (iteratorposition, värde)` eller motsvarande): Detta är o (n) - linjär tid . Här är varför:
1. Hitta positionen: Om iteratorn ges direkt är det vanligtvis o (1) att hitta positionen inom den befintliga vektorn. Men om du måste * söka * efter införingspunkten (t.ex. infoga i en sorterad ordning), kan själva söktiden vara O (n) eller O (log N) beroende på sökalgoritmen som används (linjär sökning respektive binär sökning). Men den skiftande delen dominerar.
2. skiftande element: För att ge plats för det nya elementet måste alla element * efter * införingspunkten flyttas till höger till höger. I värsta fall (infogning i början) måste du flytta "n" -element. I det genomsnittliga fallet (infogning i mitten) skiftar du ungefär `n/2 'element. I båda fallen bidrar växlingsoperationen o (n) tidskomplexitet.
Sammanfattningstabell:
| Insättningsplats | Tidskomplexitet | Förklaring |
| ---------------------- |
| Slut (push_back) | O (1) (amorterad) | Vanligtvis konstant tid. Omfördelning kan ibland behövas, men över många insättningar förblir den genomsnittliga tiden nära konstant. |
| Specifik position | O (n) | Kräver att flytta alla element efter införingspunkten. Skiftningsoperationen dominerar tidskomplexiteten. Obs:Om införingspunkten måste hittas genom att söka inom vektorn, skulle den söktiden läggas till den totala komplexiteten. |
Viktiga överväganden:
* omfördelning: När en vektor slutar på kapacitet måste den omfördela ett större minneblock och kopiera alla befintliga element till det nya blocket. Denna omfördelning är O (n). Vektorer fördubblar emellertid ofta sin kapacitet varje gång de omfördelar, vilket gör omfördelningen tillräckligt sällsynt för att kostnaden amorteras över många införingar.
* vektorimplementering: Specifikationerna för vektorimplementeringar kan påverka prestandan något. Till exempel kan vissa implementeringar använda mer sofistikerade minneshanteringstekniker.
Exempel (C ++):
`` `cpp
#include
#include
int main () {
STD ::Vector myVector ={1, 2, 3, 4, 5};
// infoga i slutet (amorterad O (1))
myvector.push_back (6);
std ::cout <<"Efter push_back:";
för (int x:myvector) std ::cout <
std ::cout <
// infoga vid en specifik position (o (n))
MyVector.Insert (MyVector.Begin () + 2, 10); // Infoga 10 vid index 2
std ::cout <<"Efter insats:";
för (int x:myvector) std ::cout <
std ::cout <
return 0;
}
`` `
Sammanfattningsvis, tänk på * där * du sätter in i en vektor. `push_back` är din vän om du bara behöver lägga till slutet. Om du behöver infoga i mitten, överväga prestationskonsekvenserna, särskilt om du gör många sådana insättningar. Om ofta medelinsättningar krävs kan alternativa datastrukturer som länkade listor eller balanserade träd vara mer lämpliga.
