Algoritmin mürəkkəbliyini necə qiymətləndirmək və ya…

Algoritmanın karmaşıklığını değerlendirmek için asymptotik analiz kullanılır, bu algoritmanın verimliliğini giriş verilerinin boyutuna ($n$) bağlı olarak tanımlamaya olanak sağlar. Temel adımlar:

Temel işlemleri tanımlama: $n$'ye bağlı olan işlemler belirlenir (örneğin, karşılaştırmalar, atamalar, aritmetik işlemler).
İşlem sayısını hesaplama: $n$'ye bağlı temel işlemlerin sayısı hesaplanır. Bu, kesin formül veya tahmin olabilir.
Asimptotik sınıfı belirleme: Büyük O ($O$), Omega ($\Omega$) və Theta ($\Theta$) sembolleri kullanılarak üst, alt və dəqiq asymptotik davranışlar təsvir edilir.

$O(f(n))$: Algoritm $f(n)$ ilə çarpılmış sabit ilə məhdudlaşdırılır və böyük $n$ üçün keçərlidir. Ən pis vəziyyət üçün istifadə olunur.
$\Omega(f(n))$: Algoritm $f(n)$ ilə çarpılmış sabit ilə ən azı məhdudlaşdırılır və böyük $n$ üçün keçərlidir. Ən yaxşı vəziyyət üçün istifadə olunur.
$\Theta(f(n))$: Algoritm $f(n)$ ilə proporsional vaxtda işləyir və böyük $n$ üçün keçərlidir. Orta və ya ən yaxşı və ən pis vəziyyətlərin eyni asymptotik sıralamaya malik olduğu hallarda istifadə olunur.

Ən çox istifadə olunan Big O üst sərhədini təsvir edir və algoritmin ən pis halda necə işlədiyini anlamaqda vacibdir.

Sabitlər və kiçik üzvləri nəzərə almamaq: Asimptotik təyin edərkən, sabit çarpanlar və aşağı dərəcəli üzvlər nəzərə alınmır, çünki böyük $n$ üçün ən böyük göstəriciyə malik funksiya üstün gəlir. Məsələn, $3n^2 + 5n + 10$ üçün asymptotik $O(n^2)$ olacaq.

Tipik asymptotik siniflər (artım sırasına görə):

$O(1)$: Sabit mürəkkəblik (iş vaxtı $n$-dən asılı deyil).
$O(\log n)$: Logarifmik mürəkkəblik (iş vaxtı $n$ ilə çox yavaş artır, məsələn, ikili axtarış üçün).
$O(n)$: Xətti mürəkkəblik (iş vaxtı $n$ ilə doğru orantılı, məsələn, sadə keçid üçün).
$O(n \log n)$: Xətti-logarifmik mürəkkəblik (səmərəli sıralama algoritmləri üçün, məsələn, Quick Sort və ya Merge Sort).
$O(n^2)$: Kvadrat mürəkkəblik (iş vaxtı $n^2$ ilə artır, məsələn, Bubble Sort kimi sadə sıralama üçün).
$O(n^c)$ (c > 1 üçün): Polinomiyal mürəkkəblik.
$O(c^n)$ (c > 1 üçün): Üsli mürəkkəblik (iş vaxtı çox sürətlə artır, məsələn, bütün mümkün variantların yoxlanması üçün).
$O(n!)$: Faktoriyal mürəkkəblik (ən yüksək sinif, çox sürətlə artır).

Döngü strukturları üçün asymptotik təyin:

Sıralı kod blokları: Blokların mürəkkəbliyi toplanır. $O(A+B) = O(\max(A, B))$.
İç içə döngülər: Təkrarlanma sayı çoxaldılır. $n$ iterasiyalı döngü içində başqa bir döngü $m$ iterasiyalıdırsa, $O(n \times m)$. Əgər $m=n$ isə, $O(n^2)$.
Giriş ölçüsünü azaldan döngülər: Məsələn, hər iterasiyada 2-yə bölmə logarifmik mürəkkəbliyə gətirir ($O(\log n)$).

Nümunə:

Sadə massiv keçidi:

# Əsas əməliyyatların yenidən hesablanması (müqayisələr, təyin etmələr)
# Əsas əməliyyat - döngüdə müqayisə
def find_max(arr):
    if not arr:
        return None
    max_val = arr[0]  # 1 təyin etmə (döngü xaricində)
    for i in range(1, len(arr)): # $n-1$ dəfə icra olunur
        # Döngü daxilində:
        # 1 müqayisə (if arr[i] > max_val)
        # ehtimal ki, 1 təyin etmə (max_val = arr[i])
        if arr[i] > max_val:
            max_val = arr[i]
    return max_val

Əgər massiv ölçüsü $n = \texttt{len(arr)}$, döngü $n-1$ dəfə işləyir. Hər iterasiyada sabit sayda əməliyyat yerinə yetirilir. Ümumi əməliyyat sayı $n$ ilə orantılıdır. Asimptotik mürəkkəblik: $O(n)$.

Nümunə: Əlavə ilə sıralama (Insertion Sort)

# Əsas əməliyyatların yenidən hesablanması
# Əsas əməliyyatlar: müqayisələr və təyin etmələr/hərəkətlər

def insertion_sort(arr):
    # Xarici döngü $n-1$ dəfə işləyir
    for i in range(1, len(arr)):
        key = arr[i] # 1 təyin etmə
        j = i - 1 # 1 təyin etmə
        # Daxili döngü ən pis halda $i$ dəfə işləyir
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j] # 1 təyin etmə (hərəkət)
            j -= 1 # 1 çıxma və 1 təyin etmə
        arr[j + 1] = key # 1 təyin etmə

Xarici döngü $n-1$ dəfə işləyir. Daxili döngü ən pis halda (dizi tərs sıralanıbsa) hər dəfə $i$ dəfə işləyir. Bütün iterasiyalar üzrə daxili döngünün əməliyyatlarının ümumi sayı: $1 + 2 + ... + (n-1) \approx n^2/2$. Asimptotik mürəkkəblik: $O(n^2)$ ən pis və orta hallarda, $O(n)$ ən yaxşı halda (dizi artıq sıralanıb). Qiymətləndirmədə adətən ən pis vəziyyət ($Büyük $O$) nəzərə alınır.

Algoritmin mürəkkəbliyini necə qiymətləndirmək və ya onun asymptotasını necə müəyyən etmək olar?