Verze z 23. 8. 2014, 02:45 editovat Jj14 (diskuse \| příspěvky) Prověření uživatelé 88 592 editací →‎Problém funkce: reformulace ; jak se překládá "problém funkce"?? ← Přejít na předchozí porovnání		Verze z 23. 8. 2014, 02:53 editovat zrušit editaci Jj14 (diskuse \| příspěvky) Prověření uživatelé 88 592 editací →‎Měření velikosti vstupu: poopraveno, ale nepřesné Přejít na další porovnání →
Řádek 33: 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)\|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. === Měření velikosti (zdrojů) ===

Teorie složitosti: Porovnání verzí