Skip to content

Latest commit

 

History

History
113 lines (81 loc) · 8.05 KB

07_casova_narocnost_algoritmu.md

File metadata and controls

113 lines (81 loc) · 8.05 KB
Raw

07. - Časová náročnost algoritmů

Časová náročnost algoritmů. Průměrné a nejhorší chování. Úlohy P, NP a NP-úplné.

  • Máme funkci f(n) a snažíme se popsat její asymptotické chování.
  • Časová složitost se také označuje jako asymptotická složitost.
  • Kromě časové složitosti se někdy určuje i paměťová náročnost.
  • Používá se symbolika:
    • \mathcal{O} ... velké O
    • \Omega ... velké omega
    • \Theta ... velké theta
  • f: \mathbb{N} \rightarrow \mathbb{R}^+
  • g: \mathbb{N} \rightarrow \mathbb{R}^+

Porovnání složitostí

V tabulce seřazeno od nejrychlejší po nejnáročnější.

Notace Název Příklad algoritmu
\mathcal{O}(1) konstantní nalezení prvku v hashovací tabulce
\mathcal{O}(\log n) logaritmická vyhledání prvku metodou půlení intervalu v seřazeném poli
\mathcal{O}(n) lineární vyhledání prvku v neseřazeném poli
\mathcal{O}(n \cdot \log n) linearitmická merge sort
\mathcal{O}(n^2) kvadratická řazení pole výběrem
\mathcal{O}(n^3) kubická násobení matic
\mathcal{O}(2^n) exponenciální
\mathcal{O}(n!) faktoriálová problém obchodního cestujícího hrubou silou
\mathcal{O}(n^n)

\mathcal{O} (Velké O)

  • Omezuje růst funkce shora
  • Používá se nejčastěji pro udávání asymptotické složitosti algoritmů (oproti ostatním dvěma notacím)
  • Říká, že funkce f neroste rychleji než kladný násobek funkce g

Zápis

f(n) \in \mathcal{O}(g(n)) (f(n) je prvkem velkého \mathcal{O}(g(n))) právě tehdy, když:

\exists K > 0 ~ \exists n_0~\forall n > n_0 ~ f(n) \leq K \cdot g(n)

\Omega (Velké omega)

  • Omezuje růst funkce zdola
  • Říká, že funkce f roste alespoň tak rychle jako g (až na multiplikativní konstantu)

Zápis

f(n) \in \Omega(g(n)) \leftrightarrow \exists K > 0 ~ \exists n_0 ~ \forall n > n_0 ~ f(n) \geq K \cdot g(n)

\Theta (Velké theta)

  • Omezuje růst funkce shora i zdola
  • Říká, že funkce f roste stejně rychle jako funkce g (až na multiplikativní konstanty)

Zápis

f(n) \in \Theta(g(n)) \leftrightarrow \exists K_1, K_2 > 0 ~ \exists n_0 ~ \forall n > n_0 ~ K_1 \cdot g(n) \leq f(n) \leq K_2 \cdot g(n)

Průměrná a nejhorší složitost

  • V praxi se často udává
    • Nejhorší složitost ... složitost, v nejhorším možném případě
    • Průměrná složitost ... složitost úlohy v průměrném případě
  • Tyto hodnoty nemusí být stejné
  • Zatímco složitost v nejhorším případě lze analyticky spočítat, průměrnou složitost je u řady algoritmů nutno zjistit statisticky.

Příklad

  • Quick sort

    • Nejhorší složitost \mathcal{O}(n^2)
    • Průměrná složitost \mathcal{O}(n \cdot \log n)
    • Závisí na vhodné volbě pivota
    • V praxi se algoritmus používá, protože ve většině případů funguje rychle a je jednoduchý na implementaci

  • Vyhledávání prvku v nesetříděném poli

    • Nejhorší složitost \mathcal{O}(n)
    • Průměrná složitost \mathcal{O}(\frac{n}{2})
    • Pozn. autora: Zde to asi nemá význam příliš rozlišovat, jelikož se jedná o stejnou složitost, která se liší pouze konstantou.

Amortizovaná složitost

Příklad: dynamické pole

  • Vložení prvku má nejhorší časovou složitost \mathcal{O}(n), protože při přidání prvku může být potřeba zvětšit velikost celého pole
  • Reálně se ovšem po zvětšení pole vložení dalších n prvků nijak nezpomalí
  • Amortizovaná složitost "rozpočítá" náročnost n operací mezi n prvků. V tomto případě by došlo n krát k vložení (konstnatní složitost) a k jednomu rozšíření pole (lineární složitost). Tyto složitosti se sečtou a vydělí počtem prvků.
  • Ve výsledku je amortizovaná složitost vkládání do dynamického pole \mathcal{O}(1).

Úlohy P, NP, NP-úplné

Porovnání P, NP, NP-úplných úloh

Video na youtube

  1. Úlohy P (polynomial time)
  • Úlohy řešitelné v polynomiálním čase \mathcal{O}(f(n)) \subset \mathcal{O}(n^k)
  • Příklady:
    • Násobení
    • Řazení
  1. Úlohy NP (non-deterministic polynomial time)
  • Úlohy, jejichž řešení lze ověřit v polynomiálním čase
  • Patří sem všechny úlohy z P, ale kromě toho i další, které už nepatří do P, např.:
    • Faktorizace - rozklad na prvočísla (asymetrická kryptografie)
    • Návrh desek plošných spojů
    • Problém obchodního cestujícího
  1. Úlohy NP-úplné
  • Jsou úlohy, které jsou NP, nejsou P a lze na ně převést všechny ostatní NP úlohy
  • Pokud by se našlo řešení NP-úplné úlohy, které by bylo schopné řešit danou úlohu v polynomiálním čase, znamenalo by to, že P = NP (všechny NP úlohy bychom dokázali vyřešit v polynomiálním čase)
  • Konsenzus je, že P \neq NP, ale zatím to nebylo dokázáno (jedná se o jeden z Millenium Prize Problems)