Junior
Siyahıdakı elementlərlə əməliyyatların asymptotik mürəkkəbliyi nədir?
sobes.tech Süni İntellekt
AI-dan cavab
Sıra tipi və əməliyyat növündən asılıdır.
Adətən aşağıdakı sıra növləri nəzərdən keçirilir:
- Sadə bağlı siyahı
- İki tərəfdən bağlı siyahı
- Array (sıra kimi xüsusi hal)
Əməliyyatlar:
- İndeksə görə giriş
- Əlavə etmək
- Silmək
- Dəyəri axtarmaq
| Əməliyyat | Sadə bağlı siyahı | İki tərəfdən bağlı siyahı | Array |
|---|---|---|---|
| İndeksə görə giriş | O(n) | O(n) | O(1) |
| Əlavə etmək | O(1) (başlanğıcda) | O(1) (başlanğıc/son) | O(n) |
| Silmək | O(n) | O(n) | O(n) |
| Dəyəri axtarmaq | O(n) | O(n) | O(n) |
İzahlar:
- O(1) (Sabit vaxt): Əməliyyat, siyahının ölçüsündən asılı olmayaraq, sabit vaxt alır. Məsələn, arraydə indeksə görə elementə giriş.
- O(n) (Xətti vaxt): Əməliyyatın icra müddəti, siyahının ölçüsü ilə proporsionaldır. Məsələn, sıralanmamış siyahıda element axtarışı.
- O(log n) (Logarifmik vaxt): Əməliyyatın icra müddəti, siyahının ölçüsü ilə logarifmik şəkildə artır. Tez-tez sıralanmış məlumatlarla işləyərkən rast gəlinir (məsələn, ikili axtarış).
Ətraflı:
- Sadə bağlı siyahıda: başlanğıca əlavə - O(1). Son və ya indeksi ilə əlavə və ya silmə, siyahını istənilən elementə qədər keçməyi tələb edir, bu da O(n) edir.
- İki tərəfdən bağlı siyahıda: başlanğıca və sona əlavə - O(1). Verilən mövqedə əlavə və ya silmə - O(1), lakin bu düyünü dəyər və ya indeks ilə tapmaq - O(n).
- Array-də: indeksi ilə giriş - O(1). Ortadakı elementə əlavə və ya silmə, elementləri sürüşdürməyi tələb edir, bu da O(n) edir. Sona əlavə və ya silmə, əgər yaddaş rezervasiya olunubsa (məsələn,
std::vectordə müəyyən bir tutumla), orta hesabla O(1) ola bilər, lakin ən pis halda (yenidən ayırma) O(n).