Verze z 18. 3. 2011, 19:54 editovat Ptbotgourou (diskuse \| příspěvky) 15 724 editací m r2.6.5) (robot změnil: es:Teoría de la complejidad computacional ← Přejít na předchozí porovnání		Verze z 20. 6. 2011, 20:47 editovat zrušit editaci 78.128.196.3 (diskuse) →‎Měření složitosti vstupu: Oprava chyby: místo multiplikativní konstanty měl být exponent; trochu vylepšena typografie, ale stejně by to chtělo lépe zacházet s matematikou Přejít na další porovnání →
Řádek 28: 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í]] <math>\mathcal{T}(''n'')</math>. Například pokud n je [[Polynom\|polynomiální]] pak hovoříme o polynomiálním algoritmu pro všechny vstupy ''n''. [[Cobhamova věta]] ří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}(ncn^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í