Odpověď
Algoritmus je polynomický (má dobu běhu polynomu), pokud pro nějaké $ k, C > 0 $, jeho doba běhu na vstupech velikosti $ n $ je maximálně $ Cn ^ k $. Ekvivalentně je algoritmus polynomický, pokud u některých $ k > 0 $ je jeho doba běhu na vstupech velikosti $ n $ $ O (n ^ k) $. To zahrnuje lineární, kvadratické, kubické a další. Na druhou stranu, algoritmy s exponenciální dobou chodu nejsou polynomiální.
Mezi nimi jsou věci – například nejznámější algoritmus pro factoring běží v čase $ O (\ exp (Cn ^ {1 / 3} \ log ^ {2/3} n)) $ pro nějakou konstantu $ C > 0 $; taková doba běhu je známá jako subexponenciální . Jiné algoritmy by mohly běžet v čase $ O (\ exp (A \ log ^ C n)) $ pro některé $ A > 0 $ a $ C > 1 $ a ty se označují jako kvazi-polynomy . Takový algoritmus byl velmi nedávno nárokován pro diskrétní logování přes malé charakteristiky.
Komentáře
- Viz také zde .
- Co jsou k a C?
- Jsou to parametry.
- Takže algoritmy s konstantním časem jsou považovány za polynomiální, správně?
- Algoritmy s konstantním časem jsou zvláštním případem polynomiálních časových algoritmů.
Odpověď
Spuštění algoritmu může zabrat nějaký výpočetní čas. Záleží hlavně na tom, jak složitý je algoritmus. Počítačoví vědci vytvořili způsob, jak klasifikovat algoritmus na základě jeho chování, kolik operací musí provést (více operací zabírá více času).
Jedna z těchto tříd ukazuje polynomiální časovou složitost. Tj. Provozní složitost je úměrná $ n ^ c $, zatímco n je velikost vstupu ac je nějaká konstanta. Název zřejmě pochází kvůli $ n ^ c $, což je polynomial .
Existují i jiné „typy“ algoritmů, které zabírají konstantní čas bez ohledu na velikost vstupu. Některé zabírají $ 2 ^ n $ času (ano, většinu času opravdu slllooooww).
Právě jsem to laikovi zjednodušil a mohl jsem zavést chyby. Přečtěte si tedy více https://stackoverflow.com/questions/4317414/polynomial-time-and-exponential-time
Komentáře
- Na Wolframu jsem četl, že polynomiální časové algoritmy jsou považovány za " rychlé " . Slyšel jsem však, že mnoho lidí říká, že upřednostňují logaritmické nebo lineární časové algoritmy před polynomiálními časovými algoritmy. Nepochopil jsem použití slova " rychle "?
- logaritmické a lineární jsou také polynomy. Myslím, že ' rychle ' pravděpodobně znamená něco jako ' mnohem pravděpodobnější, že to bude praktické skutečné použití '.
odpověď
Laicky řečeno doba běhu vašeho algoritmu.
Pořadí algoritmů (růst) může být v Big-oh (O), malém-oh (o), omega (Ω) nebo theta (Θ).
Pokud máte potíže s výpočtem RR, přečtěte si prosím několik otázek, na které jsem se předtím zeptal, a hlasujte, pokud rozumíte.
Řekněme, že máte smyčku for:
for(i=1 to n) x++ Pořadí nebo časová složitost tohoto kódu je: O (n)
Proč big-oh? Protože chceme nejhorší případ, kdy tento kus kódu běží.
Přečtěte si zde (definují složitost algoritmu a informují vás o tom, jak se algoritmy provádějí v polynomiálním čase):
http://en.wikipedia.org/wiki/NP_(complexity) http://en.wikipedia.org/wiki/NP-complete http://en.wikipedia.org/wiki/NP-hard Souhrn:
http://www.multiwingspan.co.uk/a23.php?page=types
Komentáře
- To ' přesně neodpovídá na otázku: polynomiální čas není " doba běhu vašeho algoritmu ". Místo toho může být runtime algoritmu polynomiální atd. Odpověď byste mohli vylepšit tím, že ji zpřesníte. Například si opravdu potřebujeme přečíst 3 články z Wikipedie o něčem, nebo dokonce vůbec potřebujeme vědět něco o Big Oh?