Algoritmická složitost

Algoritmická složitost

• Měří, kolik času nebo prostoru algoritmus potřebuje v závislosti na velikosti vstupu.

Příklad

• Pro seřazení pole o $n$ prvcích je nutné se na každý prvek podívat alespoň jednou, takže složitost algoritmu je minimálně $n$.

Definice

• $f(n) = O(g(n))$ pokud existují konstanty $c$ a $n_0$ takové, že pro všechna $n > n_0$ platí $f(n) \le c \cdot g(n)$.
  • $O(g(n))$ je řád algoritmu.

Běžné řády

• $O(1)$: Konstantní (přístup k prvku pole).
• $O(\log n)$: Logaritmický (binární vyhledávání).
• $O(n)$: Lineární (procházení pole).
• $O(n \log n)$: "n log n" (dobré třídicí algoritmy).
• $O(n^2)$: Kvadratický (jednoduché třídicí algoritmy).
• $O(n^3)$: Kubický (násobení matic).
• $O(2^n)$: Exponenciální (zkoušení všech možností).
• $O(n!)$: Faktoriál (zkoušení všech pořadí).

Porovnání řádů

• Konstantní čas je neměnný velikostí vstupu.
• Logaritmický čas roste velmi pomalu.
• Lineární čas roste lineárně.
• $n \log n$ roste mírně rychleji než lineární.
• Kvadratický roste ještě rychleji.
• Exponenciální roste velmi rychle.
• Faktoriál roste rychleji než exponenciální.

Jak najít řád algoritmu

• Zjistit, co algoritmus dělá.
• Určit, co je vstup.
• Zjistit, kolik kroků algoritmus provede jako funkci velikosti vstupu.
• Vzít nejvýznamnější člen.
• Ignorovat konstantní faktory.

Příklad

int sum = 0;
for (int i = 0; i < n; i++) {
  sum += i;
}

• Algoritmus provede $n$ kroků, takže je $O(n)$.

Příklad

int sum = 0;
for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++) {
    sum += i * j;
  }
}

• Algoritmus provede $n^2$ kroků, takže je $O(n^2)$.

Příklad

int sum = 0;
for (int i = 0; i < n; i++) {
  for (int j = 0; j < i; j++) {
    sum += i * j;
  }
}

• Algoritmus provede $n(n + 1) / 2$ kroků, takže je $O(n^2)$.

Logaritmické algoritmy

• Problém se v každém kroku dělí konstantním faktorem.

Příklad: Binární vyhledávání

• Hledání čísla v seřazeném poli se provádí tak, že se podíváme na prostřední prvek. Pokud je číslo menší, vyhledáváme v levé polovině, jinak v pravé polovině.
• Každý krok dělí velikost problému 2, takže trvá $O(\log n)$ kroků.

Užitečná fakta

• Algoritmus, který prochází všechny podmnožiny množiny o $n$ prvcích, je $O(2^n)$.
• Algoritmus, který prochází všechny permutace množiny o $n$ prvcích, je $O(n!)$.
• Sečtení čísel od $1$ do $n$ je $n(n + 1) / 2 = O(n^2)$.
• Sečtení mocnin 2 od $1$ do $n$ je $2n - 1 = O(n)$.

NP-úplné problémy

• Pro některé problémy neznáme efektivní algoritmy a nazýváme je NP-úplné problémy.
• Pokud lze jeden NP-úplný problém převést na jiný NP-úplný problém v polynomiálním čase, jsou ekvivalentní.

Příklady

• Problém obchodního cestujícího.
• Problém batohu.
• Problém splnitelnosti booleovských formulí (Boolean Satisfiability Problem).