Kā novērtēt algoritma sarežģītību vai noteikt tā…

Algoritmu sarežģītības novērtēšanai izmanto asymptotisko analīzi, kas ļauj aprakstīt algoritma efektivitāti atkarībā no ievades datu lieluma ($n$). Galvenie soļi:

Pamatdarbību noteikšana: Izvēlas darbības, kuru izpildes laiks būtiski atkarīgs no $n$ (piemēram, salīdzinājumi, piešķīrumi, aritmētiskās operācijas).
Darbību skaita aprēķins: Aprēķina pamatdarbību skaitu atkarībā no $n$. Tas var būt precīza formula vai novērtējums.
Asymptotiskās klases noteikšana: Tiek izmantoti Lielā O ($O$), Omega ($\Omega$) un Tēta ($\Theta$) apzīmējumi, kas raksturo augšējo, apakšējo un precīzo asymptotisko uzvedību.

$O(f(n))$: Algoritms darbojas laika, kas nepārsniedz konstantu, reizinātu ar $f(n)$, lieliem $n$. Tiek izmantots, lai raksturotu sliktāko gadījumu.
$\Omega(f(n))$: Algoritms darbojas laika, kas nav mazāks par konstantu, reizinātu ar $f(n)$, lieliem $n$. Tiek izmantots, lai raksturotu labāko gadījumu.
$\Theta(f(n))$: Algoritms darbojas laika, kas proporcionāls $f(n)$, lieliem $n$. Tiek izmantots, lai raksturotu vidējo gadījumu vai kad labākais un sliktākais gadījums ir vienāds asymptotiskais kārtība.

Visbiežāk tiek izmantots Lielais $O$, lai aprakstītu augšējo laika robežu, kas ir svarīgi, lai saprastu algoritma mērogojamību sliktākajā gadījumā.

Konstantu un mazāko locekļu ignorēšana: Noteikt asymptotiku, ignorējot konstantus koeficientus un zemākas kārtas locekļus, jo lieliem $n$ dominē lielākās pakāpes funkcija. Piemēram, $3n^2 + 5n + 10$ asymptotika būs $O(n^2)$.

Tipiskas asymptotiskās klases (augošā secībā pēc sarežģītības):

$O(1)$: Konstanta sarežģītība (izpildes laiks neatkarīgs no $n$).
$O(\log n)$: Logaritmiska sarežģītība (izpildes laiks ļoti lēni pieaug ar $n$, raksturīga binārās meklēšanas algoritmam).
$O(n)$: Līnijas sarežģītība (izpildes laiks tieši proporcionāls $n$), raksturīga vienkāršai pārbaudei.
$O(n \log n)$: Līnijas-logaritmiska sarežģītība (raksturīga efektīvām kārtošanas algoritmām, piemēram, Quick Sort vai Merge Sort).
$O(n^2)$: Kvadrātiska sarežģītība (izpildes laiks pieaug kvadrātā $n$, raksturīga vienkāršiem kārtošanas algoritmiem, piemēram, Bubble Sort).
$O(n^c)$ (c > 1): Polinomiska sarežģītība.
$O(c^n)$ (c > 1): Eksponenta sarežģītība (izpildes laiks ļoti strauji pieaug ar $n$, raksturīga visu iespējamās variācijas pārbaudei).
$O(n!)$: Faktoriāla sarežģītība (visaugstākā sarežģītības klase, ļoti strauji augoša).

Lai noteiktu ciklisko struktūru asymptotiku:

Secīgi koda bloki: Sarežģītība summējas. $O(A+B) = O(\max(A, B))$.
Iegultie cikli: Iterāciju skaits tiek reizināts. Cikls ar $n$ iterācijām, kura iekšpusē ir cits ar $m$ iterācijām, ir ar sarežģītību $O(n \times m)$. Ja $m=n$, tad sarežģītība ir $O(n^2)$.
Cikli ar datu lieluma samazināšanu: Piemēram, dalīšana ar 2 katrā iterācijā noved pie logaritmiskas sarežģītības ($O(\log n)$).

Piemērs:

Vienkārša masīva pārbaude:

# Pamatdarbību skaita aprēķins (salīdzinājumi, piešķīrumi)
# Galvenā operācija - salīdzinājums ciklā
def find_max(arr):
    if not arr:
        return None
    max_val = arr[0]  # 1 piešķiršana (ārpus cikla)
    for i in range(1, len(arr)): # Cikls tiek izpildīts $len(arr) - 1$ reizes
        # Iekš cikla:
        # 1 salīdzinājums (if arr[i] > max_val)
        # iespējams, 1 piešķiršana (max_val = arr[i])
        if arr[i] > max_val:
            max_val = arr[i]
    return max_val

Ja masīva lielums ir $n = \texttt{len(arr)}$, cikls tiek izpildīts $n-1$ reizi. Katras iterācijas laikā tiek izpildīts konstants operāciju skaits. Kopējais operāciju skaits ir proporcionāls $n$. Asymptotiskā sarežģītība: $O(n)$.

Piemērs: Iekšējās kārtošanas (Insertion Sort)

# Pamatdarbību skaita aprēķins
# Galvenās operācijas: salīdzinājumi un piešķīrumi/perkēli
def insertion_sort(arr):
    # Ārējais cikls tiek izpildīts $n-1$ reizes
    for i in range(1, len(arr)):
        key = arr[i] # 1 piešķiršana
        j = i - 1 # 1 piešķiršana
        # Iekšējais cikls tiek izpildīts sliktākajā gadījumā $i$ reizes
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j] # 1 piešķiršana (perēšana)
            j -= 1 # 1 atņemšana un 1 piešķiršana
        arr[j + 1] = key # 1 piešķiršana

Ārējais cikls tiek izpildīts $n-1$ reizes. Iekšējais cikls sliktākajā gadījumā (masīvs ir sakārtots pretējā secībā) vidēji izpildās $i$ reizes. Kopā visām ārējā cikla iterācijām operāciju skaits iekšējā cikla laikā ir aptuveni $1 + 2 + ... + (n-1) \approx n^2/2$. Asymptotiskā sarežģītība: $O(n^2)$ sliktākajā un vidējā gadījumā, $O(n)$ labākajā gadījumā (ja masīvs jau ir sakārtots). Par sarežģītības novērtējumu parasti pieņem sliktāko gadījumu (Lielais $O$).

Kā novērtēt algoritma sarežģītību vai noteikt tā asimptotu?