Eksponenta tempo

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 algoritmo 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ŭ 

 Eksponento
 Eksponenta funkcio
 Komputa komplikteorio
 Granda O
 Konstanta tempo
 Lineara tempo
 Kvadrata tempo
 Polinoma tempo
 Algoritmo

Kategorio:Komputa komplikeco

he:סיבוכיות זמן#זמן ריצה מעריכי