Junior
Jaka jest asymptotyczna złożoność operacji na klasie std::vector w C++?
sobes.tech AI
Odpowiedź od AI
Złożoność asymptotyczna dla głównych operacji z std::vector:
| Operacja | Średni czas | Najgorszy czas |
|---|---|---|
Dostęp do elementu ([], at) |
O(1) | O(1) |
| Wstawianie/usuwanie na końcu | O(1) | O(N) |
| Wstawianie/usuwanie na początku/środku | O(N) | O(N) |
Pobranie rozmiaru (size) |
O(1) | O(1) |
Zmiana rozmiaru (resize) |
O(N) | O(N) |
Wyjaśnienia:
- O(1) (czas stały): Operacja wykonywana jest w stałej liczbie kroków, niezależnie od rozmiaru wektora.
- O(N) (czas liniowy): Czas wykonania operacji jest proporcjonalny do liczby elementów w wektorze (N).
Dodatkowo:
- Wstawianie/usuwanie na końcu może wymagać O(N) w najgorszym przypadku z powodu realokacji pamięci, gdy obecna pojemność jest niewystarczająca. Podczas realokacji tworzony jest nowy, większy bufor, a wszystkie istniejące elementy są kopiowane do niego. Dzięki strategii alokacji pamięci (zazwyczaj podwajanie pojemności), średni czas wstawiania/usuwania na końcu wynosi O(1).
- Wstawianie/usuwanie w środku wymaga przesunięcia wszystkich kolejnych elementów, co zajmuje O(N) czasu.
Przykład realokacji przy push_back:
// Załóżmy, że wektor ma pojemność 4 i jest pełny
std::vector<int> vec = {1, 2, 3, 4}; // Pojemność = 4, Rozmiar = 4
// Dodanie nowego elementu wymaga realokacji
vec.push_back(5); // Może po zmianie pojemności na 8, wszystkie elementy są kopiowane
// Operacja push_back w tym przypadku zajęła O(N) czasu,
// gdzie N to liczba elementów przed realokacją.