Procházet otázky :: SZZ na MFF UK

#

- Hlavní strana
- Okruhy
- Projít
- Stáhnout
- Co je potřeba
- Chci přispět
- Kredity

Hledat:

## Prohlížení státnicových textů

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

Definice (časová složitost)

Časovou složitostí algoritmu rozumíme závislost jeho časových nároků na velikosti konkrétních vstupních dat. Analogicky se definuje i paměťová složitost. Dobu zpracování úlohy o velikosti značíme
Časovou složitost často zkoumáme z několik hledisek:

- v nejhorším případě - maximální počet operací pro nějaká data,
- v nejlepším případě - minimální počet operací pro nějaká data,
- v průměrném (očekávaném) případě - průměr pro všechna možná vstupní data (někdy též střední hodnota náhodné veličiny ).

Poznámka

Jako jednu operaci, nebo-li krok algoritmu rozumíme jednu elementární operaci nějakého abstraktního stroje (např. Turingova stroje), proveditelnou v konstantním čase. Intuitivně je možné chápat to jako několik operací počítače, které dohromady netrvají více, než nějakou pevně danou dobu.

Poznámka

Časová složitost problému je rovna složitosti nejlepšího algoritmu řešícího daný problém.

Subsections

- Asymptotická složitost
- Amortizovaná složitost