Как да оценим сложността на алгоритъм или да…

За оценка на сложността на алгоритъма се използва асимптотичен анализ, който позволява да се опише ефективността на алгоритъма в зависимост от размера на входните данни ($n$). Основните стъпки:

Определяне на основните операции: Избира се операции, чиято времева сложност значително зависи от $n$ (например сравнения, присвоявания, аритметични операции).
Броене на броя на операциите: Изчислява се броят на основните операции в зависимост от $n$. Това може да бъде точна формула или оценка.
Определяне на асимптотичния клас: Използват се обозначенията Голямо О ($O$), Омега ($\Omega$) и Тета ($\Theta$) за описание на горната, долната и точната асимптотична стойност съответно.

$O(f(n))$: Алгоритъмът се изпълнява за време, което не превишава константа, умножена по $f(n)$, при големи $n$. Използва се за описание на най-лошия случай.
$\Omega(f(n))$: Алгоритъмът се изпълнява за време, което не е по-малко от константа, умножена по $f(n)$, при големи $n$. Използва се за описание на най-добрия случай.
$\Theta(f(n))$: Алгоритъмът се изпълнява за време, пропорционално на $f(n)$, при големи $n$. Използва се за описание на средния случай или когато най-добрият и най-лошият случай имат еднакъв асимптотичен ред.

Най-често се използва Голямо $O$ за описание на горната граница на времето за изпълнение, което е важно за разбиране на мащабируемостта на алгоритъма в най-лошия сценарий.

Игнориране на константи и по-малки членове: При определяне на асимптотиката се игнорират константните множители и по-малките членове, тъй като при големи $n$ доминира функцията с най-голям показател. Например, за $3n^2 + 5n + 10$, асимптотиката ще бъде $O(n^2)$.

Типични асимптотични класове (в ред на нарастване на сложността):

$O(1)$: Константна сложност (времето за изпълнение не зависи от $n$).
$O(\log n)$: Логаритмична сложност (времето за изпълнение расте много бавно с нарастването на $n$, характерно за алгоритми за двоично търсене).
$O(n)$: Линейна сложност (времето за изпълнение е пропорционално на $n$, характерно за простия обхват).
$O(n \log n)$: Линейно-логаритмична сложност (характерна за ефективни алгоритми за сортиране, като Quick Sort или Merge Sort).
$O(n^2)$: Квадратична сложност (времето за изпълнение расте с квадрата на $n$, характерна за прости алгоритми за сортиране, като Bubble Sort).
$O(n^c)$ (за $c > 1$): Полиномиална сложност.
$O(c^n)$ (за $c > 1$): Експоненциална сложност (времето за изпълнение расте много бързо с нарастването на $n$, характерна за обхождане на всички възможни варианти).
$O(n!)$: Факториална сложност (най-високият клас сложност, расте изключително бързо).

За определяне на асимптотиката на циклични структури:

Последователни блокове код: Сложността на блоковете се събира. $O(A+B) = O(\max(A, B))$.
Вложени цикли: Броят на итерациите се умножава. Цикъл с $n$ итерации, вътре в който има друг цикъл с $m$ итерации, има сложност $O(n \times m)$. Ако $m=n$, сложността е $O(n^2)$.
Цикли с намаляване на размера на входните данни: Например, деление на 2 при всяка итерация води до логаритмична сложност ($O(\log n)$).

Пример:

Прост обхождане на масив:

# Броене на основните операции (сравнения, присвоявания)
# В този случай, основната операция е сравнение в цикъла
def find_max(arr):
    if not arr:
        return None
    max_val = arr[0]  # 1 присвояване (вън от цикъла)
    for i in range(1, len(arr)): # Цикъл се изпълнява $len(arr) - 1$ пъти
        # Вътре в цикъла:
        # 1 сравнение (if arr[i] > max_val)
        # потенциално 1 присвояване (max_val = arr[i])
        if arr[i] > max_val:
            max_val = arr[i]
    return max_val

Ако размерът на масива е $n = \texttt{len(arr)}$, цикълът се изпълнява $n-1$ пъти. Във всяка итерация се изпълнява константна брой операции. Общият брой операции е пропорционален на $n$. Асимптотична сложност: $O(n)$.

Пример: Сортиране чрез вмъкване (Insertion Sort)

# Броене на основните операции
# Основни операции: сравнения и присвоявания/премествания на елементи
def insertion_sort(arr):
    # Външният цикъл се изпълнява $n-1$ пъти
    for i in range(1, len(arr)):
        key = arr[i] # 1 присвояване
        j = i - 1 # 1 присвояване
        # Вътрешният цикъл се изпълнява в най-лошия случай $i$ пъти
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j] # 1 присвояване (преместване)
            j -= 1 # 1 изваждане и 1 присвояване
        arr[j + 1] = key # 1 присвояване

Външният цикъл се изпълнява $n-1$ пъти. В най-лошия случай (масивът е сортиран в обратен ред) вътрешният цикъл се изпълнява средно $i/2$ пъти (или до $i$ пъти). Общият брой операции във вътрешния цикъл за всички итерации на външния цикъл е: $1 + 2 + ... + (n-1) \approx n^2/2$. Асимптотичната сложност е: $O(n^2)$ в най-лошия и средния случаи, $O(n)$ в най-добрия случай (когато масивът вече е сортиран). При оценка на сложността обикновено се разглежда най-лошият случай (Голямо $O$).

Как да оценим сложността на алгоритъм или да определим неговата асимптота?