Zaman və məkan çətinliyi real məsələlərdə

8.1 Real problemlərin nümunələri və onların mürəkkəblik təhlili.

Alqoritmlərin zaman və məkan mürəkkəbliyi effektiv proqram həllərinin hazırlanmasında əsas rol oynayır. Gəlin, bu anlayışların müxtəlif sahələrdən olan real problemlərə necə tətbiq edildiyini nəzərdən keçirək.

Real problemlərin nümunələri və onların mürəkkəblik təhlili

1. Verilənlər bazasında axtarış:
   • Məsələ: Verilənlər bazasında konkret bir qeyd tapmaq.
   • Mürəkkəblik təhlili: Əgər qeydlər açar üzrə sıralanıbsa, zaman mürəkkəbliyi O(log n) olan binary search istifadə oluna bilər. Əgər sıralanmayıbsa, zaman mürəkkəbliyi O(n) olan linear search istifadə olunmalıdır.
   • Məkan mürəkkəbliyi: O(1), çünki əlavə yaddaş tələb olunmur.
2. Böyük verilənlərin emalı:
   • Məsələ: Veb server loglarının məlumatlarını təhlil edərək anomaliyaları aşkar etmək.
   • Mürəkkəblik təhlili: Analizdən əvvəl məlumatların sıralanması O(n log n) zaman mürəkkəbliyinə malik olan quick sort və ya merge sort kimi alqoritmlərlə həyata keçirilə bilər.
   • Məkan mürəkkəbliyi: Merge sort üçün O(n), quick sort üçün O(log n).
3. Qrafın dolanması:
   • Məsələ: Şəhər yolları qrafında ən qısa yolu tapmaq.
   • Mürəkkəblik təhlili: Dijkstra alqoritminin istifadə olunması, matrislərdə O(V^2) zaman mürəkkəbliyinə və ya adjacency list üçün O(E + V log V) mürəkkəbliyə malikdir.
   • Məkan mürəkkəbliyi: Zirvələrə olan məsafələrin yadda saxlanması üçün O(V).
4. Şəkillərin sıxılması:
   • Məsələ: Keyfiyyəti itirmədən şəkili sıxmaq.
   • Mürəkkəblik təhlili: Zaman mürəkkəbliyi O(n log n) olan Huffman sıxma alqoritmi kimi itkisiz sıxma alqoritmindən istifadə.
   • Məkan mürəkkəbliyi: Ara məlumatların saxlanması üçün O(n).

8.2 Mürəkkəbliyin analizinə əsaslanaraq alqoritmin seçimi.

Mürəkkəbliyin analizinə əsaslanaraq alqoritmləri necə seçmək olar?

1. Tələbləri müəyyənləşdirmək:
   • Məsələniz üçün nəyin daha vacib olduğunu müəyyənləşdirin: icra sürəti (zaman mürəkkəbliyi) ya yaddaş istifadəsi (məkan mürəkkəbliyi).
2. Verilənlərin xüsusiyyətləri:
   • Verilənlərin ölçüsünü və strukturunu nəzərə alın. Kiçik verilənlər dəstləri üçün daha az effektiv alqoritmlərdən, məsələn, bubble sort istifadə edə bilərsiniz, amma böyük verilənlər üçün daha effektiv alqoritmlərdən, məsələn, quick sort istifadə etmək daha yaxşıdır.
3. Ən pis, orta və ən yaxşı halların analizi:
   • Ən pis, orta və ən yaxşı hallarda zaman mürəkkəbliyini nəzərə alın. Məsələn, quick sort orta mürəkkəbliyə malikdir O(n log n), amma ən pis halda mürəkkəbliyi O(n^2) olur.
4. Yaddaş və resurslar:
   • Mövcud resursları və yaddaşı nəzərə alın. Məsələn, merge sort əlavə O(n) yaddaş tələb edir, amma quick sort O(log n) əlavə yaddaşla işləyə bilər.

Zaman və məkan mürəkkəbliyini nəzərə alaraq real vəzifələrin optimizasiyası

1. Daha effektiv alqoritmlərin istifadəsi:
   • Daha az effektiv alqoritmlərin daha effektivlə əvəz olunması. Məsələn, sıralanmış verilənlər üçün xətkeş axtarış yerinə binary search istifadə etmək.
2. Döngü və iterasiyaların optimizasiyası:
   • Döngülərdə əməliyyatların sayını minimuma endirmək və lazımsız hesablamaları çıxarmaq. Məsələn, dinamik proqramlama üçün memoization istifadə etmək.
3. Müvafiq verilənlər strukturlarının istifadəsi:
   • Verilənlərə sürətli giriş üçün hash-table istifadə etmək və ya qaydalı verilənlər üçün axtarış ağaclarından istifadə etmək.
4. Verilənlərin paralel emalı:
   • Məsələni paralel icra edilə bilən alt məsələlərə bölmək. Məsələn, paralel merge sort.

8.3 Həqiqi problemlərdə zaman mürəkkəbliyi

1. Məlumatların axtarılması və çeşidlənməsi

İkili axtarış (O(log n)):

Çeşid edilmiş massivdə və ya verilənlər bazasında elementin axtarılması üçün istifadə olunur. Yerinə yetirilmə vaxtı məlumatların ölçüsünün loqarifmasına bağlanır, bu da onu böyük məlumat həcmləri üçün son dərəcə effektiv edir.

Nümunə:

Kitabxananın çeşid edilmiş verilənlər bazasında kitabı onun koduna görə axtarmaq.

Sürətli çeşidləmə (O(n log n)):

Çoxsaylı praktik hallarda ən sürətli çeşidləmə alqoritmlərindən biridir. Müntəzəm məlumat çeşidlənməsi tələb olunan sistemlərdə, məsələn, verilənlər bazası idarəetmə sistemlərində (DBMS) istifadə olunur.

Nümunə:

İnternet-mağazada sifarişləri daxil olma tarixinə görə çeşidləmək.

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)
        

2. Qraflar və şəbəkələr

Dijkstra alqoritmi (O(V^2)):

Qrafda ən qısa yolları tapmaq üçün istifadə olunur. GPS kimi naviqasiya sistemlərində marşrutların qurulmasında tətbiq edilir.

Nümunə:

Xəritədə iki nöqtə arasında ən qısa marşrutu qurmaq.

import heapq

def dijkstra(graph, start):
    queue = [(0, start)]
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
            
    while queue:
        current_distance, current_vertex = heapq.heappop(queue)
            
        if current_distance > distances[current_vertex]:
            continue
            
        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight
            
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(queue, (distance, neighbor))
            
    return distances
        

3. Şəkillərin emalı

Konvolyusiya neyron şəbəkələri (CNN) alqoritmi (O(n^2)):

Kompüter görmə problemləri üçün maşın öyrənməsində istifadə olunur, məsələn, obyektlərin tanınması və şəkillərin təsnifatı.

Nümunə:

Təhlükəsizlik sistemində üz tanıma.

8.4 Reallıqdakı tapşırıqlarda məkan mürəkkəbliyi.

1. Böyük məlumatlarla iş

Keşləşdirmə (O(n)):

Tez-tez tələb olunan məlumatları yadda saxlamaqla həmin məlumatlara girişin sürətlənməsi məqsədiylə keşləşdirmədən istifadə edirik. Məkan mürəkkəbliyi, yadda saxlanmalı olan məlumatların miqdarından asılıdır.

Misal:

Məlumat bazasındakı sorğuların nəticələrinin keşləşdirməsi ilə təkrarlanan sorğuların sürətləndirilməsi.

cache = {}
def get_data_from_cache(key):
    if key in cache:
        return cache[key]
    else:
        data = fetch_data_from_db(key)  # Gəlin, bunu məlumat bazasından məlumat alma funksiyası kimi təsəvvür edək
        cache[key] = data
        return data
        

2. Dinamik proqramlaşdırma

Fibonacci ədədlərini hesablama alqoritmi (O(n)):

Artıq hesablanmış dəyərləri saxlamaq üçün əlavə yaddaşdan istifadə edir, bu da zaman mürəkkəbliyini eksponensialdan xətti səviyyəyə qədər endirir.

Misal:

Logistika üzrə optimal marşrutların hesablanması.

def fibonacci(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 2:
        return 1
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
    return memo[n]
        

3. Maşın öyrənməsi

Modellərin öyrədilməsi (O(n^2) və daha yüksək):

Xətti reqressiya və ya dərin neyron şəbəkələr kimi maşın öyrənməsi modellərinin öyrədilməsi, parametrlərin və aralıq hesablamaların saxlanması üçün əhəmiyyətli yaddaş tələb edir.

Misal:

Alıcı davranışlarını proqnozlaşdırmaq üçün modelin öyrədilməsi.