Subeksponencijalno vreme

S Vikipedije, slobodne enciklopedije

U teoriji složenosti, subeksponencijalno vreme je vreme izvršavanja algoritama koje je veće od polinomijalnog vremena (superpolinomijalno vreme), ali manje od eksponencijlanog vremena. Jedan primer je najbolji poznati, klasični algoritam za faktorizaciju celih brojeva koji zahteva približno Algoritmi koji zahtevaju subeksponencijalno vreme se smatraju računarski neizvodljivim za velike vrednosti ulaza.

Algoritam čiji ulaz ima dužinu n je subeksponencijalni algoritam, ako je za njegovo izvršavanje u najgorem slučaju potrebno vreme veličine .

Vidi još[uredi | uredi izvor]