Hogyan értékeljük egy algoritmus összetettségét vagy…

Algoritmus összetettségének értékeléséhez aszimptotikus elemzést alkalmaznak, amely lehetővé teszi az algoritmus hatékonyságának leírását a bemeneti adatok méretének ($n$) függvényében. A fő lépések:

Alapműveletek meghatározása: Azokat a műveleteket választják ki, amelyek futási ideje jelentősen függ a $n$ értékétől (például összehasonlítások, hozzárendelések, aritmetikai műveletek).
Műveletszám számítása: A $n$ függvényében számítják ki az alapműveletek számát. Ez lehet pontos képlet vagy becslés.
Aszimptotikus osztály meghatározása: A Nagy O ($O$), Omega ($\Omega$) és Theta ($\Theta$) jelöléseket használják a felső, alsó és pontos aszimptotikus viselkedés leírására.

$O(f(n))$: Az algoritmus olyan idő alatt fut, amely nem haladja meg a $f(n)$ szorozva egy konstanssal, nagy $n$ esetén. A legrosszabb eset leírására használják.
$\Omega(f(n))$: Az algoritmus legalább $f(n)$ szorozva egy konstanssal fut, nagy $n$ esetén. A legjobb eset leírására használják.
$\Theta(f(n))$: Az algoritmus időben arányos $f(n)$-nel, nagy $n$ esetén. Átlagos eset vagy amikor a legjobb és legrosszabb eset ugyanazon aszimptotikus sorrendben van.

A leggyakrabban használt Nagy O a futási idő felső határának leírására szolgál, ami fontos az algoritmus skálázhatóságának megértéséhez a legrosszabb esetben.

Állandók és kisebb tagok figyelmen kívül hagyása: Az aszimptotikánál figyelmen kívül hagyják az állandó szorzókat és az alacsonyabb rendű tagokat, mivel nagy $n$ esetén a legnagyobb hatású függvény dominál. Például, $3n^2 + 5n + 10$ esetén az aszimptotika $O(n^2)$ lesz.

Tipikus aszimptotikus osztályok (növekvő komplexitás szerint):

$O(1)$: Állandó komplexitás (az idő nem függ $n$-től).
$O(\log n)$: Logaritmikus komplexitás (az idő nagyon lassan növekszik a $n$-nel, jellemző a bináris keresés algoritmusára).
$O(n)$: Lineáris komplexitás (az idő arányos $n$-nel, jellemző az egyszerű keresésre).
$O(n \log n)$: Lineáris-logaritmikus komplexitás (hatékony rendezési algoritmusokra jellemző, például Quick Sort vagy Merge Sort).
$O(n^2)$: Négyzetes komplexitás (az idő $n^2$-vel növekszik, jellemző a Bubble Sorthoz vagy más egyszerű rendezési algoritmushoz).
$O(n^c)$ (c > 1): Polinomialis komplexitás.
$O(c^n)$ (c > 1): Exponenciális komplexitás (az idő nagyon gyorsan növekszik, például az összes lehetőség átvizsgálásával).
$O(n!)$: Faktoriális komplexitás (a legmagasabb osztály, rendkívül gyors növekedés).

A ciklikus struktúrák aszimptotikus meghatározásához:

Szekvenciális kódrészek: A blokkok összetettségét összeadják. $O(A+B) = O(\max(A, B))$.
Beágyazott ciklusok: Az iterációk száma szorozva. Egy $n$ iterációs ciklusban, amelyben egy másik $m$ iterációs ciklus van, az összetettség $O(n \times m)$. Ha $m=n$, akkor $O(n^2)$.
Adatbevitel csökkentő ciklusok: Például, minden iterációban 2-vel való osztás logaritmikus komplexitást eredményez ($O(\log n)$).

Példa:

Egyszerű tömb átvizsgálása:

# Alapműveletek újraszámítása (összehasonlítások, hozzárendelések)
# Fő művelet - összehasonlítás a ciklusban
def find_max(arr):
    if not arr:
        return None
    max_val = arr[0]  # 1 hozzárendelés (a cikluson kívül)
    for i in range(1, len(arr)): # $n-1$ alkalommal
        # A cikluson belül:
        # 1 összehasonlítás (if arr[i] > max_val)
        # potenciálisan 1 hozzárendelés (max_val = arr[i])
        if arr[i] > max_val:
            max_val = arr[i]
    return max_val

Ha a tömb mérete $n = \texttt{len(arr)}$, a ciklus $n-1$ alkalommal fut. Minden iterációban állandó számú művelet történik. Az összes művelet száma arányos $n$-nel. Aszimptotikus összetettség: $O(n)$.

Példa: Beszúró rendezés (Insertion Sort)

# Alapműveletek újraszámítása
# Fő műveletek: összehasonlítások és hozzárendelések/mozgatások

def insertion_sort(arr):
    # Külső ciklus $n-1$ alkalommal fut
    for i in range(1, len(arr)):
        key = arr[i] # 1 hozzárendelés
        j = i - 1 # 1 hozzárendelés
        # Belső ciklus a legrosszabb esetben $i$ alkalommal
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j] # 1 hozzárendelés (mozgatás)
            j -= 1 # 1 kivonás és 1 hozzárendelés
        arr[j + 1] = key # 1 hozzárendelés

A külső ciklus $n-1$ alkalommal fut. A belső ciklus a legrosszabb esetben (ha a tömb fordított sorrendben van) minden alkalommal $i$-szer fut. Az összes iteráció során a belső ciklus műveleteinek össz-száma: $1 + 2 + ... + (n-1) \approx n^2/2$. Aszimptotikus összetettség: $O(n^2)$ a legrosszabb és középső esetekben, $O(n)$ a legjobb esetben (ha a tömb már rendezett). Az összetettség értékelésekor általában a legrosszabb esetet veszik figyelembe (Nagy $O$).

Hogyan értékeljük egy algoritmus összetettségét vagy határozzuk meg az aszimptotikáját?