Rekursiv alqoritmlərin mürəkkəbliyi

5.1 Rekursiv alqoritmlərin çətinliyinin analizi.

Rekursiv alqoritmlər mürəkkəb məsələlərin həlli üçün güclü bir vasitədir, onları daha sadə alt-məsələlərə bölməyə imkan verir. Amma rekursiv alqoritmlərin çətinliyinin analizi iterativ alqoritmlərlə müqayisədə daha çətin ola bilər. Rekursiv alqoritmlərin analizində nəzərə alınmalı olan əsas məqamlar vaxt və yaddaş çətinliyini əhatə edir.

Bu qiymətləndirmələr alqoritmin giriş məlumatlarının ölçüsündən asılı olaraq nə qədər vaxt və yaddaş tələb etdiyini göstərir. Rekursiv alqoritmlərin çətinliyinin təhlili çox vaxt alqoritmin davranışını təsvir edən rekurrent tənliklərin tərtib və həll olunmasını əhatə edir.

Rekursiv alqoritmlərin vaxt çətinliyi:

Rekursiv alqoritmlərin vaxt çətinliyi çox vaxt onun rekursiv çağırışlarının yerinə yetirilmə vaxtını təsvir edən rekurrent münasibətlərdən istifadə etməklə analiz edilir.

Rekurrent tənlik:

Rekurrent tənlik — bu bir tənlikdir, hansı ki, alqoritmin vaxt çətinliyini giriş məlumatlarının daha kiçik ölçüsü üçün vaxt çətinliyi ilə ifadə edir. Bu, rekursiv alqoritmin icrası üçün tələb olunan vaxtı təsvir etməyə kömək edir.

Nümunələr:

• T(n) = T(n − 1) + O(1)
• T(n) = 2T(2n) + O(n)

5.2 Rekursiv alqoritm tapşırıqlarına nümunələr.

Nümunə 1: Ədədin faktorialı

Ədədin faktorialını hesablayan alqoritmi nəzərdən keçirək:

def factorial(n):
    if n == 0:

        return 1

    else:

        return n * factorial(n - 1)
        

Bu alqoritm üçün rekurrent asılılıq belə yazıla bilər:

T(n) = T(n − 1) + O(1)

Bu tənliyin həlli:

T(n) = O(n)

Beləliklə, faktorial alqoritminin vaxt mürəkkəbliyi O(n)-ə bərabərdir.

Nümunə 2: Sürətli çeşidləmə

Sürətli çeşidləmə alqoritmini nəzərdən keçirə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)
        

Bu alqoritm üçün orta halda rekurrent asılılıq belədir:

• T(n) = 2 * T(n / 2) + O(n)

Master metodunu istifadə edərək bu tənliyin həlli:

• T(n) = O(n * log(n))

5.3 Rekursiv alqoritmlərin məkan mürəkkəbliyi

Rekursiv alqoritmlərin məkan mürəkkəbliyi dəyişənlərin saxlanması üçün istifadə olunan yaddaşın və çağırışlar steki üçün istifadə olunan yaddaşın cəmi kimi müəyyən edilir. Dərin rekursiv alqoritmlərdə çağırışlar kontekstini saxlamaq üçün böyük miqdarda yaddaş istifadə oluna bilər.

Məsələn: Fibbonacci

Fibbonacci ədədlərini hesablamaq üçün alqoritmi nəzərdən keçirək:

def fibonacci(n):
    if n <= 1:

        return n

    else:

        return fibonacci(n - 1) + fibonacci(n - 2)
        

Vaxt mürəkkəbliyi üçün rekurrent nisbət:

• T(n) = T(n − 1) + T(n − 2) + O(1)

Bu tənliyin həlli:

• T(n) = O(2n)

Məkan mürəkkəbliyi isə maksimum rekursiv çağırış dərinliyi ilə müəyyən edilir, bu halda O(n).

5.4 Rekursiv alqoritmlərin mürəkkəbliyini təhlil metodları

Rekursiv alqoritmlərin mürəkkəbliyini təhlil metodları

1. Əvəzləmə metodu:
• Həll formasını təsəvvür etmək və induksiya ilə sübut üçün istifadə olunur.
• o Nümunə: Rekurrent tənliklərin həlli üçün əvəzləmə metodu.
2. 2. Rekursiya ağacı metodu:
   • Rekursiv çağırışları ağac şəklində vizuallaşdırır, burada hər bir düyün funksiyanın çağırışını təsvir edir.
   • Nümunə: Rekursiv çağırışlarla sürətli çeşidləmə.
3. Master metodu:
   • T(n) = a * T(n / b) + f(n) formasındakı rekurrent tənlikləri analiz etmək üçün şablondur.
   • Nümunə: Sürətli çeşidləmə.

Rekursiv alqoritmlərin mürəkkəbliyini təhlil etmək həm vaxt, həm də məkan mürəkkəbliyini nəzərə almağı tələb edir. Rekurrent əlaqələrin başa düşülməsi və əvəzləmə, rekursiya ağacı metodu və master metod kimi təhlil metodlarının tətbiqi rekursiv alqoritmlərin performansını dəqiq qiymətləndirməyə kömək edir.