Skaičiavimo sudėtingumo teorijoje daugianario laiko mažinimas yra vienos problemos sprendimo metodas naudojant kitą. Polinominio laiko sumažinimas dažnai naudojamas sudėtingumo teorijoje apibrėžiant sudėtingumo klases ir visas tų klasių problemas. …
Kas laikomas daugianario laiku?
Laikoma, kad algoritmas yra daugianario laiko, jei jo vykdymo laikas viršutinėje dalyje yra ribojamas algoritmo įvesties dydžio daugianario išraiškos, ty T(n)=O(nk) kai kuriai teigiamai konstantai k.
Kaip žinoti, ar kažkas yra daugianario laikas?
3 Atsakymai. Algoritmas yra polinominis (turi daugianario veikimo laiką), jei kurio nors k atveju, C>0, jo veikimo laikas n dydžio įvestyse yra daugiausia Cnk. Lygiai taip pat algoritmas yra polinomas, jei kai kurių k>0 atveju jo veikimo laikas n dydžio įvestyse yra O(nk).
Kas atsitiks, jei sumažinimas leidžiamas eksponentiniu laiku?
Jei sumažinimui leidžiamas eksponentinis laikas, jis gali visiškai išspręsti pradinę problemą ir sukurti trivialų tikslinės problemos egzempliorių Tai reiškia, kad kiekviena NP problema yra redukuojama į kiekvieną Kita tokio tipo mažinimo problema, todėl kiekviena NP problema yra NP pilna eksponentiniam laiko sumažinimui.
Kas yra eksponentinis algoritmas?
Sakoma, kad algoritmas yra eksponentinis laikas, jei T(n) viršutinė riba yra 2poly( ) , kur poli(n) yra koks nors n daugianomas. Formaliau kalbant, algoritmas yra eksponentinis laikas, jei T(n) ribojasi su O(2nk), kai kuri nors konstanta k. Ref:Wiki.
