Algoritmus, problém, časová složitost algoritmu v nejhorším a průměrném případě

Algoritmus

• Algoritmus je posloupnosti instrukcí pro řešení problému
  • $\Rightarrow$ vede k dalším otázkám
  • Instrukce je jednoznačný srozumitelný pokyn
  • Řešení problému algoritmem = vykonáváním instrukcí podle algoritmu se od vstupu $I$ po konečném počtu kroků dobereme k výstupu $O$

Tip

Pojem algoritmus je podobně jako pojem množina základním pojmem, který není definován pomocí jednodušších pojmů, je jen objasňován svými vlastnostmi na konkrétních příkladech.

Problém

• Definice problém:
  • Problém je určen trojicí $(IN,OUT,p)$, kde $IN$ je množina (přípustných) vstupů, $OUT$ je množina výstupů a $p:IN\to OUT$ je funkce přiřazující každému vstupu odpovídající výstup

Příklad problému

Název: Dosažitelnost vrcholů v grafu Vstup: Neorientovaný/Orientovaný graf $G=(V,E)$ a vrchol $s\in V$ Výstup: Jsou všechny vrcholy $v\in V$ dosažitelné z $s$?

Časová složitost algoritmu v nejhorším případě a v průměrném případě

• Vyjadřuje závislost trvání výpočtu daného algoritmu na velikosti vstupních dat
• Funkce, která velikosti vstupních dat přiřadí trvání výpočtu $$\begin{array}{c}n\\ ⋮\\ \text{velikost vstupu}\end{array}\to \begin{array}{c}T(n)\\ ⋮\\ \text{trvaˊnıˊ vyˊpocˇtu}\end{array}$$
• $T(n)$ lze chápat dvěma základními možnostmi:
  1. Časová složitost v nejhorším případě
     • $T(n)$ znamená délku výpočtu algoritmu $A$ nad vstupem velikosti $n$ v nejhorším případě;
     • $T(n)=\text{max}\{k\mid k\text{ je deˊlka vyˊpocˇtu }A\text{ nad vstupem velikost }n\}$
  2. Časová složitost v průměrném případě
     • $T(n)$ znamená délku výpočtu algoritmu $A$ nad vstupem velikosti $n$ v průměrném případě;
     • $T(n)=\frac{t_A(i_1)+...+t_A(i_m)}{m}$
     • $t_A(i)$ je počet elementárních výpočetních kroků vykonaných od zahájení do skončení výpočtu algoritmem $A$ pro vstup $i$

Navigace

Předchozí: Geometrická interpretace určitého integrálu Následující: O-notace a růst funkcí, definice, vlastnosti, příklady použití Celý okruh: 1. Teoretické základy informačních technologií