Toto je starší verze dokumentu!
—-
Časová složitost
Vyjadřuje závislost času potřebného pro provedení výpočtu na rozsahu (velikosti) vstupních dat.
Rozlišujeme časovou složitost v nejlepším, nejhorším a průměrném případě.
Θ notace
—
: f roste asymptoticky stejně rychle jako g
O notace
—
: f roste asymptoticky rychleji než g
Ω notace
—
: f roste asymptoticky pomaleji než g
Permutace
Generování všech permutací n-prvkové posloupnosti
Polynom
Evaluace v bodě .
Technika pro přesnější určení složitosti.
Zásobník
Zásobník
operace | složitost | kredity |
---|---|---|
PUSH | 1 | 2 |
POP | 1 | 0 |
MULTIPOP | 0 |
Zásobník
operace | složitost | amortizovaná cena |
---|---|---|
PUSH | 1 | |
POP | 1 | |
MULTIPOP |
Operace | Seznam | Binární halda | Binomiální halda | Fibonacciho halda |
---|---|---|---|---|
MAKE_HEAP | ||||
MINIMUM | ||||
INSERT | * | |||
UNION | ||||
EXTRACT_MIN | * | |||
DELETE | * | |||
DECREASE_KEY | * |
* amortizovaná složitost
Algoritmy pro:
Algoritmus | Předspracování | Vyhledávání |
---|---|---|
Úplné prohledávání | ||
Karp-Rabin * | ||
Konečné automaty | ||
Knuth-Morriss-Pratt | ||
Boyer-Moore * |
* Průměrná složitost je výrazně lepší.