Junior
C++'ta std::vector sınıfıyla işlemlerin asimptotik karmaşıklığı nedir?
sobes.tech yapay zeka
AI'dan gelen yanıt
std::vector ile temel işlemler için asimptotik karmaşıklık:
| İşlem | Ortalama zaman | En kötü zaman |
|---|---|---|
Öğeye erişim ([], at) |
O(1) | O(1) |
| Sonuna ekleme/silme | O(1) | O(N) |
| Başlangıca/ortaya ekleme/silme | O(N) | O(N) |
Boyutu alma (size) |
O(1) | O(1) |
Boyutu değiştirme (resize) |
O(N) | O(N) |
Açıklamalar:
- O(1) (sabit zaman): İşlem, vektörün boyutundan bağımsız olarak sabit sayıda adımda gerçekleştirilir.
- O(N) (doğrusal zaman): İşlemin çalışma süresi, vektördeki öğe sayısı (N) ile doğru orantılıdır.
Ek olarak:
- Sonuna ekleme/silme, bellek yeniden tahsisi nedeniyle en kötü durumda O(N) gerektirebilir, mevcut bellek kapasitesi yetersiz olduğunda. Yeniden tahsis sırasında, daha büyük yeni bir tampon oluşturulur ve tüm mevcut öğeler kopyalanır. Bellek tahsis stratejisi (genellikle kapasiteyi iki katına çıkarma) sayesinde, ortalama ekleme/silme süresi O(1) olur.
- Ortadaki ekleme/silme, tüm takip eden öğelerin kaydırılmasını gerektirir ve bu da O(N) zaman alır.
push_back sırasında yeniden tahsis örneği:
// Diyelim ki, vektör kapasitesi 4 ve dolu
std::vector<int> vec = {1, 2, 3, 4}; // Kapasite = 4, Boyut = 4
// Yeni bir öğe eklemek yeniden tahsis gerektirir
vec.push_back(5); // Muhtemelen kapasite 8 olur ve tüm öğeler kopyalanır
// Bu durumda `push_back` işlemi O(N) zaman aldı,
// burada N, yeniden tahsis öncesi öğe sayısıdır.