Müxtəlif data strukturlarının mürəkkəblik analizi

9.1 Array-ların, siyahıların, hash cədvəllərinin mürəkkəbliyi.

Data strukturlarının mürəkkəbliyinin analizi müxtəlif əməliyyatların (məsələn, daxil etmə, silmə, axtarış) yerinə yetirilməsi üçün lazım olan vaxt və yaddaş həcminin qiymətləndirilməsinə diqqət yetirir. Mürəkkəbliyi anlamaq developer-ə müəyyən tapşırıqlar üçün ən uyğun data strukturlarını seçməyə kömək edir, resurslardan effektiv istifadəni təmin edir.

1. Array-lar (Arrays):

• İndeksə görə giriş: O(1)
• Elementin axtarışı: O(n)
• Elementin daxil edilməsi: O(n) (ən pis halda, array-in ortasına daxil etmək)
• Elementin silinməsi: O(n) (ən pis halda, array-in ortasından silmək)
• Yaddaş: O(n)

İstifadə nümunəsi: Array-lar indeksə görə sürətli giriş tələb edən ssenarilər üçün effektivdir, məsələn, cədvəllər və zaman seriyaları.

2. Linked Lists (Bağlantılı siyahılar):

• İndeksə görə giriş: O(n)
• Elementin axtarışı: O(n)
• Elementin daxil edilməsi: O(1) (əgər mövqe məlumdursa)
• Elementin silinməsi: O(1) (əgər mövqe məlumdursa)
• Yaddaş: O(n)

İstifadə nümunəsi: Linked Lists əlavə və ya silmə əməliyyatlarının tez-tez lazım olduğu hallarda faydalıdır, məsələn, növbələr və steklər implementasiyasında.

3. Hash Tables (Hash Cədvəlləri):

• Elementin axtarışı: O(1) (orta halda)
• Elementin daxil edilməsi: O(1) (orta halda)
• Elementin silinməsi: O(1) (orta halda)
• Yaddaş: O(n)

İstifadə nümunəsi: Hash Tables dictionary-lərin və açar-dəyər bazalarının implementasiyası üçün effektivdir.

9.2 Ağaçlar və qrafiklərin mürəkkəbliyi.

1. İkidəyişənli axtarış ağacları (Binary Search Trees, BST):

• Elementin axtarışı: O(log n) (orta halda)
• Elementin əlavə olunması: O(log n) (orta halda)
• Elementin silinməsi: O(log n) (orta halda)
• Yaddaş: O(n)

İstifadə nümunəsi: Axtarış ağacları məlumat bazalarında və strukturlarında, məsələn, çoxluqlar və xəritələrdə (map) istifadə olunur.

2. Qrafiklər (Graphs):

• Eninə axtarış (BFS): O(V + E)
• Dərinliyinə axtarış (DFS): O(V + E)
• Ən qısa yol (Dijkstra): O(V^2) ya da O(E + V log V) qonşuluq siyahısı üçün
• Yaddaş: O(V + E)

İstifadə nümunəsi: Qrafiklər şəbəkə marşrutlaşdırmalarında, sosial şəbəkələrdə, əlaqə analizində və qrafik məlumat bazalarında istifadə olunur.

9.3 Uyğun verilənlər strukturunu seçmək

Mürəkkəblik analizinə əsasən verilənlər strukturlarını necə seçmək olar?

Vəzifənin xarakteristikası:

Vəzifəniz üçün ən çox istifadə olunan və kritik əməliyyatları müəyyən edin (axtarış, əlavə etmə, silmə).

Verilənlərin ölçüsü:

Verilənlərin ölçüsünü və mövcud resursları nəzərə alın. Kiçik məlumatlar üçün massivlər və əlaqəli siyahılar kimi sadə strukturlardan istifadə edə bilərsiniz.

Performansa olan tələblər:

Vəzifəniz üçün hansı daha vacibdir: əməliyyatların icra müddəti, yoxsa yaddaş istifadəsi?

Yaddaş tələbatı:

Yaddaş məhduddursa, aşağı fəzavi mürəkkəbliklə verilənlər strukturlarını seçin.

Vaxt və məkan mürəkkəbliyini nəzərə alaraq real vəzifələrin optimallaşdırılması nümunələri

Uyğun verilənlər strukturlarının istifadəsi:

Nümunə: Tez-tez axtarış əməliyyatları üçün hash-table-dən istifadə edin, tez-tez əlavə/silmə əməliyyatları üçün isə əlaqəli siyahılar.

Əməliyyatların sayının azaldılması:

Nümunə: Dövrələrin optimallaşdırılması və lazımsız hesablamaların çıxarılması, memoization və dinamik proqramlaşdırma üsullarından istifadə.

Verilənlərin paralel emalı:

Nümunə: Böyük məlumatların emalı üçün multithreading və ya paylanmış sistemlərdən istifadə.

9.4 Verilənlər strukturlarının analizi üçün hazır məsələlər.

Real məsələlərin analizi və optimizasiyası üçün praktik tapşırıqlar

Tapşırıq 1: Massivdə axtarışın optimizasiyası

Sizin 10 milyon ədədlik massiviniz var. Elementin axtarış alqoritmini optimizasiya edin.

Həll:

Sıralanmış massiv üçün binary search istifadə edin.

Tapşırıq 2: Bağlı siyahı ilə işin optimizasiyası

Sizin bağlı siyahınız var və tez-tez elementləri əlavə etməli və silməli olursunuz.

Həll:

Əlavə və silmənin optimizasiyası üçün ikitərəfli bağlı siyahı istifadə edin.

Tapşırıq 3: Hash-table-da verilənlərin işlənməsi

Verilənlərə sürətli giriş imkanı tanıyan dictionary yaradın.

Həll:

Əlavə, silmə və axtarış əməliyyatları üçün hash-table istifadə edin, zaman mürəkkəbliyi O(1) ilə.

Tapşırıq 4: Qrafın keçilməsi

Şəhər yolları qrafında ən qısa yolu tapın.

Həll:

Matris smayilli qraf üçün O(V^2) zaman mürəkkəbliyi ilə Dijkstra alqoritmi istifadə edin ya da smayilli siyahı üçün O(E + V log V).