Junior
C++-də std::vector sinfi ilə əməliyyatların asymptotik mürəkkəbliyi nədir?
sobes.tech Süni İntellekt
AI-dan cavab
std::vector ilə əsas əməliyyatların asymptotik mürəkkəbliyi:
| Əməliyyat | Orta vaxt | Ən pis vaxt |
|---|---|---|
Elementə giriş ([], at) |
O(1) | O(1) |
| Sonuna əlavə etmə/silme | O(1) | O(N) |
| Başlanğıc/orta əlavə etmə/silme | O(N) | O(N) |
Ölçünü alma (size) |
O(1) | O(1) |
Ölçünü dəyişmə (resize) |
O(N) | O(N) |
İzahlar:
- O(1) (sabit vaxt): Əməliyyat sabit sayda addımda yerinə yetirilir, vektorun ölçüsündən asılı deyil.
- O(N) (xətti vaxt): Əməliyyatın icra vaxtı vektorun elementlərinin sayına (N) birbaşa proporsionaldır.
Əlavə olaraq:
- Sonuna əlavə etmə/silme, yaddaşın yenidən ayrılması (realloc) səbəbindən ən pis halda O(N) tələb edə bilər, mövcud yaddaş tutumu kifayət etmədikdə. Yenidən ayrılma zamanı, daha böyük yeni tampon yaradılır və bütün mövcud elementlər ona köçürülür. Yaddaş ayırma strategiyası (adətən, tutumu ikiqat artırmaq) sayəsində, orta hesabla əlavə etmə/silme vaxtı O(1) olur.
- Ortada əlavə etmə/silme, bütün ardıcıl elementlərin hərəkət etdirilməsini tələb edir və bu, O(N) vaxt alır.
push_back zamanı yenidən ayırma nümunəsi:
// Tutaq ki, vektorun tutumu 4 və doludur
std::vector<int> vec = {1, 2, 3, 4}; // Tutum = 4, Ölçü = 4
// Yeni element əlavə etmək yenidən ayırma tələb edir
vec.push_back(5); // Mümkündür ki, tutum 8-ə yüksəlsin və bütün elementlər köçürülür
// Bu halda `push_back` əməliyyatı O(N) vaxt aldı,
// burada N, yenidən ayırmadan əvvəlki elementlərin sayıdır.