Polinoma tempo
En komputa komplikteorio, rula polinoma tempo de algoritmo estas okazo ke la asimptota supera baro de tempo bezonata por solvi la problemon estas polinoma funkcio al amplekso n de la datumoj donitaj kiel enigo, kie k estas iu konstanto kiu ne dependas de n por ĉiu aparta algoritmo. Do la tempo estas O(nk).
Notu, ke kvankam en polinomo la potenco k ĉiam estas entjero, en okazo de polinoma tempo estas konsiderataj ne nur entjeraj k, sed ĉiuj reelaj k≥0.
Kelkaj oftaj okazoj:
| k | Kalkulada tempo | Ekzemplo |
|---|---|---|
| 0 | Konstanta tempo O(1) | Difini ĉu nombro estas para aŭ nepara |
| a por ĉiu a>0 | Logaritma tempo O(log n) | Trovo de ero en ordigita listo per duoniga serĉa algoritmo |
| 1 | Lineara tempo O(n) | Adicio de du n-ciferaj nombroj. Trovo de ero en neordigita n-era listo. |
| 1+a por ĉiu a>0 | O(n log n) | Ordigo de n-era listo per piramida ordigo. Komputo de rapida konverto de Fourier. |
| 2 | Kvadrata tempo O(n2) | Multipliko de du n-ciferaj nombroj (per kutima rekta maniero). Adicio de du n×n matricoj. Ordigo de n-era listo per simpla enenigo aŭ bobelo. Rekta komputo de diskreta konverto de Fourier. |
| 3 | Kuba tempo O(n3) | Multipliko de du n×n matricoj (per kutima rekta maniero). |
Por ĉiu k>0 kaj ĉiu c>1, O(nc log(nk)) estas subaro de O(log(n(c+a))) por ĉiu a>0. Tiel ofte estanta kresko O(nc log(nk)) povas esti konsiderata kiel polinoma kun malmulte pli granda potenco.
Oni iam uzas la nocion de "polinoma tempo de longo de la enigo" kiel difino de "rapida" aŭ "farebla" kalkulado, kontraŭ de super-polinoma tempo, kiu estas io pli malrapida. Eksponenta tempo estas ekzemplo de super-polinoma tempo. Kvankam reala por malgrandaj taskoj ĉi tiuj rezonoj povas esti malveraj, ĉar en ĉi tia okazo koeficientoj kaj termoj de pli malgranda ordo en formulo de tempo, malatentataj de la granda O, estas gravaj.
La komplikeco klaso de decida problemo kiu povas esti solvita per determinisma sinsekva maŝino en polinoma tempo estas P. La klaso de decida problemo kiu povas esti kontrolita en polinoma tempo estas NP. Ekvivalente, NP estas la klaso de decida problemo kiu povas esti solvita en polinoma tempo per ne-determinisma maŝino de Turing.
P estas la plej malgranda tempo-komplikeca klaso sur determinisma maŝino kiu ne ŝanĝas se modelo de la maŝino ŝanĝas. Ekzemple, ŝanĝo de unu-benda maŝino de Turing al mult-benda maŝino povas konduki al kvadrata plirapidigo, sed ĉiu algoritmo kiu ruliĝas en polinoma tempo sur unu modelo ankaŭ ruliĝas en polinoma tempo sur la alia, ĉar kvadrata radiko do polinomo estas la granda O de polinomo kaj kvadrato de polinomo estas denove polinomo. P estas ankaŭ la plej malgranda klaso fermita sub komponaĵo de subproblemoj.
Estadas uzata termino malforte polinoma rula tempo. Ĉi tiu signifas ke la tempo estas polinoma ne de amplekso de la enigo, sed de cifereca valoro de la enigo, kiu povas esti eksponente pli granda. Ekzemple, la eŭklida algoritmo estas nur malforte polinoma se estas realigita uzante subtrahon.
Simile, rula tempo estas forte polinoma se la tempo estas sendependa de la cifereca datuma amplekso kaj dependas nur de la imanentaj dimensioj de la problemo. Ekzemple, algoritmo kiu povas ordigi n entjerojn, ĉiu malpli granda ol k en tempo O(n2) estas forte polinoma, kaj algoritmo povas ordigi ilin en tempo O(nk) estas malforte polinoma (ĉar entjero malpli granda ol k povas esti prezentita en amplekso logaritma de k).