Junior
Milline on std::vector klassi operatsioonide asümptootiline keerukus C++-s?
sobes.tech AI
Vastus AI-lt
Asümptootne keerukus operatsioonidele std::vector:
| Operatsioon | Keskmine aeg | Halvim aeg |
|---|---|---|
Elementi juurdepääs ([], at) |
O(1) | O(1) |
| Lisamine/kustutamine lõpus | O(1) | O(N) |
| Lisamine/kustutamine alguses/keskel | O(N) | O(N) |
Suurus (size) saamine |
O(1) | O(1) |
Suuruse muutmine (resize) |
O(N) | O(N) |
Selgitused:
- O(1) (konstantne aeg): Operatsioon teostatakse fikseeritud arv samme, sõltumata vektori suurusest.
- O(N) (jooneline aeg): Operatsiooni täitmise aeg on otseselt proportsionaalne elementide arvuga vektoris (N).
Täiendavalt:
- Lisamine/kustutamine lõpus võib nõuda O(N) halvimatel juhtudel mälu ümberpaigutamist (reallokatsiooni), kui praegune mälu maht on ebapiisav. Reallokatsiooni ajal luuakse uus, suurem bufeer ja kõik olemasolevad elemendid kopeeritakse sinna. Mälu eraldamise strateegia (tavaliselt mahutavuse kahekordistamine) tõttu on keskmine lisamise/kustutamise aeg O(1).
- Lisamine/kustutamine keskel nõuab kõigi järgnevate elementide nihutamist, mis võtab aega O(N).
Näide reallokatsioonist push_back puhul:
// Oletame, et vektoril on maht 4 ja see on täis
std::vector<int> vec = {1, 2, 3, 4}; // Mahutavus = 4, Suurus = 4
// Uue elemendi lisamine nõuab reallokatsiooni
vec.push_back(5); // Võib-olla muutub mahutavus 8-ks, kõik elemendid kopeeritakse
// `push_back` operatsioon selles olukorras võtab O(N) aega,
// kus N on elementide arv enne reallokatsiooni.