Jak ocenić złożoność algorytmu lub określić jego…

Aby ocenić złożoność algorytmu, stosuje się analizę asymptotyczną, która opisuje efektywność algorytmu w zależności od rozmiaru danych wejściowych ($n$). Główne kroki:

Definicja operacji podstawowych: Identyfikuje się operacje, których czas wykonania znacząco zależy od $n$ (np. porównania, przypisania, operacje arytmetyczne).
Obliczenie liczby operacji: Określa się ilość operacji podstawowych w zależności od $n$. Może to być dokładna formuła lub oszacowanie.
Określenie klasy asymptotycznej: Używa się oznaczeń Wielkie O ($O$), Omega ($\Omega$) i Theta ($\Theta$) do opisania górnego, dolnego i dokładnego zachowania asymptotycznego odpowiednio.
- $O(f(n))$: Algorytm wykonuje się w czasie nie przekraczającym stałej pomnożonej przez $f(n)$ dla dużych $n$. Używa się do opisu najgorszego przypadku.
- $\Omega(f(n))$: Algorytm wykonuje się w czasie nie mniejszym niż stała pomnożona przez $f(n)$ dla dużych $n$. Używa się do opisu najlepszego przypadku.
- $\Theta(f(n))$: Algorytm wykonuje się w czasie proporcjonalnym do $f(n)$ dla dużych $n$. Używa się do opisu średniego przypadku lub gdy najlepszy i najgorszy przypadek mają ten sam porządek asymptotyczny.

Najczęściej używaną notacją jest Wielkie O ($O$), które opisuje górną granicę czasu wykonania, co jest ważne dla zrozumienia skalowalności algorytmu w najgorszym scenariuszu.

Pomijanie stałych i terminów niższego rzędu: Przy określaniu notacji asymptotycznej ignoruje się mnożniki stałe i terminy niższego rzędu, ponieważ dla dużych $n$ dominuje funkcja z największym wykładnikiem. Na przykład, dla $3n^2 + 5n + 10$, notacja asymptotyczna będzie $O(n^2)$.

Typowe klasy asymptotyczne (w kolejności rosnącej złożoności):

$O(1)$: Złożoność stała (czas wykonania nie zależy od $n$).
$O(\log n)$: Złożoność logarytmiczna (czas wykonania rośnie bardzo powoli wraz z $n$, charakterystyczne dla algorytmów wyszukiwania binarnego).
$O(n)$: Złożoność liniowa (czas wykonania jest proporcjonalny do $n$, charakterystyczne dla prostego przeszukiwania).
$O(n \log n)$: Złożoność liniowo-logarytmiczna (charakterystyczna dla efektywnych algorytmów sortowania, takich jak Quick Sort czy Merge Sort).
$O(n^2)$: Złożoność kwadratowa (czas wykonania rośnie kwadratem $n$, charakterystyczne dla prostych algorytmów sortowania, takich jak Bubble Sort).
$O(n^c)$ (dla $c > 1$): Złożoność wielomianowa.
$O(c^n)$ (dla $c > 1$): Złożoność wykładnicza (czas wykonania rośnie bardzo szybko wraz z $n$, charakterystyczne dla przeszukiwania brute-force).
$O(n!)$: Złożoność silniowa (najwyższa klasa złożoności, rośnie niezwykle szybko).

Aby określić asymptotyczną złożoność struktur cyklicznych:

Bloki kodu sekwencyjnego: Złożoność bloków się sumuje. $O(A+B) = O(\max(A, B))$.
Pętle zagnieżdżone: Liczba iteracji się mnoży. Pętla z $n$ iteracjami wewnątrz innej z $m$ iteracjami ma złożoność $O(n \times m)$. Jeśli $m=n$, to $O(n^2)$.
Pętle z redukcją rozmiaru danych wejściowych: Na przykład, dzielenie przez 2 przy każdej iteracji prowadzi do logarytmicznej złożoności ($O(\log n)$).

Przykład:

Prosta iteracja po tablicy:

# Liczba operacji podstawowych (porównania, przypisania)
# Główna operacja to porównanie w pętli
def find_max(arr):
    if not arr:
        return None
    max_val = arr[0]  # 1 przypisanie (poza pętlą)
    for i in range(1, len(arr)): # Pętla wykonuje się $n-1$ razy
        # Wewnątrz pętli:
        # 1 porównanie (if arr[i] > max_val)
        # potencjalnie 1 przypisanie (max_val = arr[i])
        if arr[i] > max_val:
            max_val = arr[i]
    return max_val

Jeśli rozmiar tablicy to $n = \texttt{len(arr)}$, pętla wykonuje się $n-1$ razy. W każdej iteracji wykonywane są operacje stałe. Całkowita liczba operacji jest proporcjonalna do $n$. Złożoność asymptotyczna: $O(n)$.

Przykład: Sortowanie przez wstawianie (Insertion Sort)

# Liczba operacji podstawowych
# Główne operacje: porównania i przypisania/przesunięcia elementów
def insertion_sort(arr):
    # Zewnętrzna pętla wykonuje się w $n-1$ przypadkach
    for i in range(1, len(arr)):
        key = arr[i] # 1 przypisanie
        j = i - 1 # 1 przypisanie
        # W najgorszym przypadku wewnętrzna pętla wykonuje się $i$ razy
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j] # 1 przypisanie (przesunięcie)
            j -= 1 # 1 odejmowanie i 1 przypisanie
        arr[j + 1] = key # 1 przypisanie

Zewnętrzna pętla wykonuje się $n-1$ razy. W najgorszym przypadku (tablica w odwrotnej kolejności), wewnętrzna pętla wykonuje się średnio $i$ razy (lub do $i$ razy). Suma operacji we wszystkich iteracjach zewnętrznej pętli to około $1 + 2 + ... + (n-1) \approx n^2/2$. Asymptotyczna złożoność: $O(n^2)$ w najgorszym i średnim przypadku, $O(n)$ w najlepszym przypadku (tablica już posortowana). Przy ocenie złożoności zwykle bierze się pod uwagę najgorszy przypadek (Wielkie $O$).

Jak ocenić złożoność algorytmu lub określić jego asymptotę?