Polinomijalno vreme

U teoriji kompleksnosti, polinomijalno vreme se odnosi na vreme izračunavanja problema, gde vreme, m(n), nije veće od polinomijalne funkcije veličine problema, n. Matematički zapisano u notaciji velikog O, ovo znači $m(n)=O(n^{k})$ gde je k neka konstanta koja može zavisiti od problema. Na primer, algoritam za sortiranje kviksort za n brojeva zahteva najviše $n^{2}$ operacija. Stoga mu je potrebno vreme $O(n^{2})$ , pa se radi o algoritmu polinomijalnog vremena.

Matematičari nekada koriste pojam polinomijalnog vremena u odnosu na dužinu ulaza kao definiciju brzog računanja, kao suprotnost super-polinomijalnom vremenu, koje se odnosi na sve šta je sporije od toga. Eksponencijalno vreme je primer super-polinomijalnog vremena.

Klasa kompleksnosti problema odlučivanja koji mogu biti rešeni determinističkom Tjuringovom mašinom u polinomijalnom vremenu je poznata kao klasa P. Klasa problema odlučivanja čije se potencijalno rešenje može proveriti u polinomijalnom vremenu je se naziva klasom NP. Ekvivalentno, NP je klasa problema odlučivanja koji se mogu rešiti u polinomijalnom vremenu nedeterminističkom Tjuringovom mašinom (NP znači Nedeterminističko Polinomijalno vreme).

Podklase polinomijalnog vremena

Konstantno vreme: O(1)
Linearno vreme: O(n)
Kvadratno vreme: O(n²)
Kubno vreme: O(n³)

Algoritmi kojima je potrebno linearno, logaritamsko i konstantno vreme su brži podskup algoritama koji zahtevaju polinomijalno vreme.

Povezano