Junior
Mekkora azimutális összetettsége van a std::vector osztály műveleteinek C++-ban?
sobes.tech MI
Válasz az MI-től
Aszimptotikus összetettség a std::vector fő műveleteihez:
| Művelet | Átlagos idő | Legrosszabb idő |
|---|---|---|
Elemhez való hozzáférés ([], at) |
O(1) | O(1) |
| Hozzáadás/törlés a végén | O(1) | O(N) |
| Hozzáadás/törlés a kezdetnél/közepén | O(N) | O(N) |
Méret lekérdezése (size) |
O(1) | O(1) |
Méret módosítása (resize) |
O(N) | O(N) |
Magyarázatok:
- O(1) (állandó idő): A művelet rögzített lépésszám alatt végrehajtható, függetlenül a vektor méretétől.
- O(N) (lineáris idő): A művelet végrehajtási ideje arányos a vektor elemeinek számával (N).
További információ:
- A végéhez való hozzáadás/törlés a memória újraelosztása miatt a legrosszabb esetben O(N) lehet, ha a jelenlegi kapacitás nem elegendő. Az újraelosztás során egy nagyobb puffer jön létre, és minden meglévő elem átkerül oda. A memóriafoglalási stratégia (általában a kapacitás duplázása) miatt az átlagos hozzáadás/törlés idő O(1).
- A közepén történő hozzáadás/törlés az összes következő elem eltolását igényli, ami O(N) időt vesz igénybe.
Példa az push_back esetén történő újraelosztásra:
// Tegyük fel, hogy a vektor kapacitása 4 és tele van
std::vector<int> vec = {1, 2, 3, 4}; // Kapacitás = 4, Méret = 4
// Új elem hozzáadása újraelosztást igényel
vec.push_back(5); // Lehet, hogy a kapacitás 8 lesz, és minden elem átkerül
// A `push_back` művelet ebben az esetben O(N) időt vett igénybe,
// ahol N a re-allokáció előtti elem számát jelenti.