Kako proceniti složenost algoritma ili odrediti…

Za procenu složenosti algoritma koristi se asimptotska analiza, koja omogućava opisivanje efikasnosti algoritma u zavisnosti od veličine ulaznih podataka ($n$). Glavni koraci:

Određivanje osnovnih operacija: Izabiraju se operacije čije vreme izvršenja znatno zavisi od $n$ (na primer, poređenja, dodeljjenja, aritmetičke operacije).
Brojanje broja operacija: Izračunava se broj osnovnih operacija u zavisnosti od $n$. To može biti tačna formula ili procena.
Određivanje asimptotske klase: Koriste se oznake Veliko O ($O$), Omega ($\Omega$) i Theta ($\Theta$) za opisivanje gornjeg, donjeg i tačnog asimptotskog ponašanja.

$O(f(n))$: Algoritam se izvršava za vreme koje ne prelazi konstantu, pomnoženu sa $f(n)$, pri velikim $n$. Koristi se za opisivanje najgoreg slučaja.
$\Omega(f(n))$: Algoritam se izvršava za vreme koje nije manje od konstante, pomnožene sa $f(n)$, pri velikim $n$. Koristi se za opisivanje najboljeg slučaja.
$\Theta(f(n))$: Algoritam se izvršava za vreme proporcionalno $f(n)$, pri velikim $n$. Koristi se za opisivanje srednjeg slučaja ili kada najbolji i najgori slučaj imaju isti asimptotski red.

Najčešće se koristi Veliko $O$ za opisivanje gornje granice vremena izvršenja, što je važno za razumevanje skalabilnosti algoritma u najgorem scenariju.

Ignorisanje konstanti i nižih članova: Pri određivanju asimptotike ignorišu se konstantni faktori i niži članovi, jer pri velikim $n$ dominira funkcija sa najvećim stepenom. Na primer, za $3n^2 + 5n + 10$, asimptotika će biti $O(n^2)$.

Tipične asimptotske klase (po rastu složenosti):

$O(1)$: Konstantna složenost (vreme izvršenja ne zavisi od $n$).
$O(\log n)$: Logaritamska složenost (vreme izvršenja raste vrlo sporo sa rastom $n$, karakteristično za algoritme binarnog pretraživanja).
$O(n)$: Linearna složenost (vreme izvršenja je proporcionalno $n$, karakteristično za jednostavno pretraživanje).
$O(n \log n)$: Linearno-logaritamska složenost (karakteristično za efikasne algoritme sortiranja, kao što su Quick Sort ili Merge Sort).
$O(n^2)$: Kvadratna složenost (vreme izvršenja raste sa kvadratom $n$, karakteristično za jednostavne algoritme sortiranja, kao što je Bubble Sort).
$O(n^c)$ (za $c > 1$): Polinomska složenost.
$O(c^n)$ (za $c > 1$): Eksponencijalna složenost (vreme izvršenja raste vrlo brzo sa rastom $n$, karakteristično za pretraživanje svih mogućih kombinacija).
$O(n!)$: Faktorijalna složenost (najviši razred složenosti, raste izuzetno brzo).

Za određivanje asimptotike cikličkih struktura:

Sekvencijalni blokovi koda: Složenost blokova se sabira. $O(A+B) = O(\max(A, B))$.
Ugnježdeni cikli: Broj iteracija se množi. Ciklus sa $n$ iteracija, unutar kojeg je drugi ciklus sa $m$ iteracija, ima složenost $O(n \times m)$. Ako je $m=n$, složenost je $O(n^2)$.
Cikli sa smanjenjem veličine ulaznih podataka: Na primer, deljenjem sa 2 pri svakoj iteraciji, što dovodi do logaritamske složenosti ($O(\log n)$).

Primer:

Jednostavno pretraživanje niza:

# Brojanje osnovnih operacija (poređenja, dodeljivanja)
# U ovom slučaju, osnovna operacija je poređenje u petlji
def find_max(arr):
    if not arr:
        return None
    max_val = arr[0]  # 1 dodeljivanje (izvan petlje)
    for i in range(1, len(arr)): # Petlja se izvršava $len(arr) - 1$ puta
        # Unutar petlje:
        # 1 poređenje (if arr[i] > max_val)
        # potencijalno 1 dodeljivanje (max_val = arr[i])
        if arr[i] > max_val:
            max_val = arr[i]
    return max_val

Ako je veličina niza $n = \texttt{len(arr)}$, petlja se izvršava $n-1$ puta. U svakoj iteraciji se izvršava konstantan broj operacija. Ukupan broj operacija je proporcionalan na $n$. Asimptotska složenost: $O(n)$.

Primer: Sortiranje umetkom (Insertion Sort)

# Brojanje osnovnih operacija
# Osnovne operacije: poređenja i dodeljivanja/premještanja elemenata
def insertion_sort(arr):
    # Spoljašnja petlja se izvršava $n-1$ puta
    for i in range(1, len(arr)):
        key = arr[i] # 1 dodeljivanje
        j = i - 1 # 1 dodeljivanje
        # Unutrašnja petlja se izvršava u najgorem slučaju $i$ puta
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j] # 1 dodeljivanje (premještanje)
            j -= 1 # 1 oduzimanje i 1 dodeljivanje
        arr[j + 1] = key # 1 dodeljivanje

Spoljašnja petlja se izvršava $n-1$ puta. U najgorem slučaju (niz je sortiran u obrnutom redosledu), unutrašnja petlja se u proseku izvršava $i/2$ puta (ili do $i$ puta). Ukupno, za sve iteracije spoljašnje petlje, broj operacija u unutrašnjoj petlji je: $1 + 2 + ... + (n-1) \approx n^2/2$. Asimptotska složenost je: $O(n^2)$ u najgorem i prosečnom slučaju, $O(n)$ u najboljem slučaju (kada je niz već sortiran). Pri proceni složenosti se obično razmatra najgori slučaj (Veliko $O$).

Kako proceniti složenost algoritma ili odrediti njegovu asimptotu?