Asymptotická složitost: Porovnání verzí
Smazaný obsah Přidaný obsah
→Typické příklady časové složitosti: jedovaté poznámky značka: editace z Vizuálního editoru |
→Třídy složitosti: ++slo6itost problmu a algoritmus, ?? nejake nedokoncene vety |
||
Řádek 8:
==Třídy složitosti==
Algoritmy můžeme podle hodnot <math>f(N)</math> nějakého kritéria rozřadit do tříd. Kritéria jsou časová a paměťová složitost, dále pro paralelní a distribuované algoritmy komunikační složitost. Rozlišuje se složitost v nejhorším případě (která se odhaduje jednodušeji) a složitost v průměrném případě. Nejčastěji, tj. implicitně, se uvažuje o časové složitosti algoritmu v nejhorším případě. Dále lze určovat{{zdroj?}}
''Složitost problému'' je složitost ''nejlepšího'' algoritmu, který ho řeší. Každý konkrétní algoritmus poskytuje horní odhad složitosti.
Řádek 24:
Jednou z největších současných otevřených otázek teoretické [[informatika|informatiky]] je problém, zda se třídy P a NP rovnají. Vše nasvědčuje tomu, že to pravda není (viz [[NP-úplnost]] a [[problém P versus NP]]).
=== Složitost algoritmů a složitost problémů===
Je dobré rozlišovat ty dvě věci uvedené v nadpisu i v tomhle článku. ''Složitost algoritmu'' je odhad složitosti konkrétního algoritmu. Obvykle nás zajímá horní odhad, případně průměrný případ. ''Složitost problému'' je složitost nejlepšího algoritmu, který problém řeší. Zde je zajímavý dolní odhad, který se dokazuje pomocí teoretických nástrojů. Přitom každý konkrétní algoritmus poskytuje horní odhad složitosti problému.
=== Typické příklady časové složitosti ===
| |||