Wiki definește Timp polinomial ca reziduu:
Se spune că un algoritm este de timp polinomial dacă timpul său de rulare este delimitat superior de o expresie polinomială în dimensiunea intrării pentru algoritm, adică $ T (n) = O (n ^ k) $ pentru o constantă $ k $
I înțelegeți că, în general, diferența dintre Timp polinomial și Timp exponențial este că funcția exponențială crește strict mai repede decât orice funcție polinomială, asimptotic ( referință ).
Încerc să înțeleg nucleul definiția timp exponențial .
- Ce elemente vor face ca un algoritm să ruleze în Timp exponențial ?
- Ce schimbare trebuie să fac în expresia polinomială to make it Timp exponențial ? (Prin it mă refer la definiția algoritmului la început a întrebării)
Comentarii
- 1. Faceți exponențial multe lucruri. 2. Folosiți polinomul ca putere a unei baze > 1.
- Nu ' nu vă înțeleg al doilea întrebare. Polinoamele sunt polinoame; exponențialele sunt exponențiale. A întreba ce trebuie să schimbi pentru a transforma un polinom într-un exponențial este ca și cum ai întreba ce trebuie să schimbi pentru a transforma un logaritm într-un cosinus. Cum puteți defini o funcție de timp exponențială în termeni de expresie polinomială?
- Funcțiile exponențiale vor exista cu siguranță dacă P = NP. Probabil că există încă probleme care ' vor lua timp exponențial chiar dacă P = NP, deși niciuna nu îmi vine în minte imediat. O funcție exponențială poate fi definită în termeni de polinom, dar acel polinom trebuie să fie infinit de lung – poate doriți să căutați Expansiuni Taylor dacă ' vă interesează acest lucru.
- @ymbirtt Chiar și cea mai ușoară versiune a teoremei ierarhiei de timp spune că nu există algoritm de timp polinomial pentru nicio problemă EXPTIME-complete. Că ' este un rezultat necondiționat: nu ' nu depinde de presupunerea că P $ \ neq $ NP.
Răspuns
-
Nu există un răspuns ușor pentru acesta, deși există semne de care trebuie să fii atent Examinarea fiecărui subset posibil al unui set, de exemplu, este exponențială – așa că dacă aș avea un set de numere întregi $ \ {x_1, …, x_n \} $ și aș dori să verific fiecare subset al acestora pentru a vedea dacă se sumează la $ 0 $, ar trebui să iau în considerare exact $ 2 ^ n $ subseturi, ceea ce face ca această metodă să fie timp exponențial. Mai multe capcane diferite pot face un algoritm timp exponențial, totuși, deci, în loc să căutați categorii largi, analizați algoritmii de la caz la caz.
-
Dacă un algoritm necesită $ n ^ 2 $ pași pentru finalizare, atunci este „polinomial. Dacă ia 2 $ ^ n $ pași, este exponențial. Diferența este poziția $ n $. Dacă ceva este $ O (n ^ m) $ pentru $ n > 1 $, $ m > 0 $, atunci este „s polinom în $ n $ pentru $ m $ fix, dar exponențial în $ m $ pentru $ n $ fix.
Comentarii
- Atenție. Funcția $ n ^ m $ nu este ' t polinom în $ n $, cu excepția cazului în care $ m $ este o constantă. Și, dacă $ m $ este o constantă, ' nu are sens să spunem că funcția este exponențială în acea constantă.
- Da, tu ' am dreptate. Am ' voi clarifica acest lucru.
Răspuns
Adesea obțineți un algoritm exponențial de forță brută în timp când luați în considerare o problemă și enumerați întregul său spațiu de căutare. variabile setate la adevărat), probleme de permutare (în TSP, fiecare tur este o permutare a orașelor) și probleme de partiție (în colorarea graficului, încercați să p artați vârfurile în clase de culori). Sau luați în considerare sortarea chiar: există $ n! $ Permutări de $ n $ întregi. Parcurgeți fiecare permutare și verificați dacă este sortată. Prost (și lent), dar funcționează.
Comentarii
- Deși rețineți că $ O (n!) $ Este chiar mai rău decât $ O ( k ^ n) $. Dacă ' tot încerci să afli despre complexitatea timpului, acesta ar putea fi un lucru util de demonstrat pentru tine.