Złożoność algorytmów rekurencyjnych

5.1 Analiza złożoności algorytmów rekurencyjnych.

Algorytmy rekurencyjne to potężne narzędzie do rozwiązywania trudnych problemów, pozwalające dzielić je na prostsze podzadania. Jednak analiza złożoności algorytmów rekurencyjnych może być bardziej skomplikowana w porównaniu do algorytmów iteracyjnych. Główne aspekty, które należy wziąć pod uwagę przy analizie algorytmów rekurencyjnych, obejmują złożoność czasową i przestrzenną.

Te oceny pokazują, ile czasu i pamięci potrzebuje algorytm w zależności od rozmiaru danych wejściowych. Analiza złożoności algorytmów rekurencyjnych często obejmuje budowę i rozwiązywanie równań rekurencyjnych, które opisują zachowanie algorytmu.

Złożoność czasowa algorytmów rekurencyjnych:

Złożoność czasowa algorytmów rekurencyjnych często analizowana jest z wykorzystaniem równań rekurencyjnych, które opisują czas wykonania algorytmu poprzez czas wykonania jego rekurencyjnych wywołań.

Równanie rekurencyjne:

Równanie rekurencyjne to równanie, które wyraża złożoność czasową algorytmu poprzez jego złożoność czasową dla mniejszych rozmiarów danych wejściowych. Pomaga opisać nakłady czasowe na wykonanie rekurencyjnego algorytmu.

Przykłady:

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

5.2 Przykłady zadań z algorytmami rekurencyjnymi.

Przykład 1: Silnia liczby

Rozważmy algorytm obliczania silni liczby n:

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

        return 1

    else:

        return n * factorial(n - 1)
        

Równanie rekurencyjne dla tego algorytmu można zapisać jako:

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

Rozwiązanie tego równania daje:

T(n) = O(n)

Zatem złożoność czasowa algorytmu silni wynosi O(n).

Przykład 2: Szybkie sortowanie

Rozważmy algorytm szybkiego sortowania:

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)
        

Równanie rekurencyjne dla tego algorytmu w przypadku średnim:

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

Rozwiązanie tego równania z użyciem metody głównej daje

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

5.3 Złożoność przestrzenna algorytmów rekurencyjnych

Złożoność przestrzenna algorytmów rekurencyjnych określana jest jako suma pamięci używanej do przechowywania zmiennych oraz pamięci używanej dla stosu wywołań. W głęboko rekurencyjnych algorytmach znaczna ilość pamięci może być użyta do przechowywania kontekstu wywołań.

Przykład: Fibonacci

Rozważmy algorytm obliczania liczb Fibonacciego:

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

        return n

    else:

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

Równanie rekurencyjne dla złożoności czasowej:

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

Rozwiązanie tego równania daje:

• T(n) = O(2n)

Złożoność przestrzenna określana jest maksymalną głębokością rekurencyjnych wywołań, która w tym przypadku wynosi O(n).

5.4 Metody analizy złożoności algorytmów rekurencyjnych

Metody analizy złożoności algorytmów rekurencyjnych

1. Metoda podstawiania:
• Używana do przypuszczenia formy rozwiązania i dowodu przez indukcję.
• Przykład: Podstawienie do rozwiązania równań rekurencyjnych.
2. 2. Metoda drzewa rekursji:
   • Wizualizacja wywołań rekurencyjnych w postaci drzewa, gdzie każdy węzeł reprezentuje wywołanie funkcji.
   • Przykład: Szybkie sortowanie z wywołaniami rekurencyjnymi.
3. Metoda główna:
   • Szablon do analizy równań rekurencyjnych w postaci: T(n) = a * T(n / b) + f(n)
   • Przykład: Szybkie sortowanie.

Analiza złożoności algorytmów rekurencyjnych wymaga uwzględnienia zarówno złożoności czasowej, jak i przestrzennej. Zrozumienie równań rekurencyjnych i zastosowanie metod analizy, takich jak podstawianie, metoda drzewa rekursji i metoda główna, pomagają dokładnie oceniać wydajność algorytmów rekurencyjnych.