Polinomijalno vreme

Iz Wikipedije, slobodne enciklopedije
Idi na navigaciju Idi na pretragu

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 gde je k neka konstanta koja može zavisiti od problema. Na primer, algoritam za sortiranje kviksort za n brojeva zahteva najviše operacija. Stoga mu je potrebno vreme , 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[uredi - уреди | uredi kôd]

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

Vidi još[uredi - уреди | uredi kôd]