Verze z 16. 7. 2014, 22:27 editovat Jj14 (diskuse \| příspěvky) Prověření uživatelé 88 592 editací →‎Zadání problému: "instance" ← Přejít na předchozí porovnání		Verze z 16. 7. 2014, 22:36 editovat zrušit editaci Jj14 (diskuse \| příspěvky) Prověření uživatelé 88 592 editací →‎Měření velikosti vstupu: ++styl Přejít na další porovnání →
Řádek 32: Závisí na množství času pro zpracování algoritmem. Tyto dílčí problémy, kterým může být i prostor potřebný pro řešení zpracovává samostatný [[algoritmus]] a vše souvisí také s velikostí vstupu v [[bit]]ech. Teorie složitosti se zajímá mimo jiné o způsob jakým se algoritmus vypořádá s velikostí vstupu. Například pro řešení souvislého grafu o ''n'' hranách v porovnání s grafem o ''2n'' hranách. Jestliže je vstupem ''n'' pak čas potřebný pro výpočet je [[Funkce (matematika)\|~~funkcí~~funkce]] <math>\mathcal{T}(n)</math>. Například pokud <math>\mathcal{T}(n)</math> je [[Polynom\|polynomiální]] pak hovoříme o polynomiálním algoritmu <s>pro všechny vstupy ''n''</s>. [[Cobhamova teze]] říká že problém lze vyřešit v polynomiálním čase, pokud pro něj existuje algoritmus, který zpracuje ''n'' bitový vstup v čase <math>\mathcal{O}(n^c)</math>, kde ''c'' je konstanta závisející na problému, nikoliv jeho vstupu. == Související články ==

Teorie složitosti: Porovnání verzí