Eksponenta tempo

El Vikipedio, la libera enciklopedio
Saltu al: navigado, serĉo

En komputa komplikteorio, eksponenta tempo estas la kalkulada tempo de problemo kiu estas barita per eksponenta funkcio de la amplekso n de la problemo.

Ĉi tio signifas ke ekzistas c > 1 tia ke la kalkula tempo m(n) = O(cn) aŭ eĉ pli konkrete (???) ekzistas k > 1 tia ke m(n) = Θ(kn)

Por grandaj n, la eksponenta tempo estas pli granda ol iu ajn polinoma tempo, do eksponenta tempo estas subscpeco de la super-polinoma tempo.

Oni iam opinias ke polinoma tempo estas sufiĉe rapida, kaj ĉiu tempo kiu estas pli granda ol polinoma tempo (super-polinoma tempo) estas malrapida. Per ĉi tiu difino, eksponenta tempo devas esti konsiderata kiel malrapida. Ĉi tio provizas utilan proksimumaĵon, sed estas malpreciza. En praktiko, la reala rula tempo de algoritmo dependas de la ordo de kresko kaj de la konstantoj en la formulo por la tempo. Por donita ne tro granda amplekso de problemo, specifa polinoma tempo povas esti pli granda ol specifa eksponenta tempo. Tamen, por sufiĉe grandaj ampleksoj de problemo, la rula tempo de algorimto kun eksponenta tempo estas pli granda.

Estas algoritmoj kiu havas rulan tempon kiu estas super-polinoma tempo (pli granda ol polinoma tempo) sed malpli granda ol eksponenta tempo (sub-eksponenta tempo). Ekzemplo estas la plej bona sciata algoritmo por faktorigo de entjero. Ankaŭ ĉi tiuj algoritmoj estas konsiderataj kiel malrapidaj.

Vidu ankaŭ[redakti | redakti fonton]