Експоненцијално време

Из Википедије, слободне енциклопедије
Иди на навигацију Иди на претрагу

У теорији комплексности, за неки проблем се каже да има експоненцијално време израчунавања ако је за његово израчунавање потребно време m(n), које је ограничено експоненцијалном функцијом величине проблема, n. Другим речима, када се величина проблема повећава линеарно, време потребно за решавање проблема се повећава експоненцијално.

Запиано математички, постоји k > 1 такво да је m(n) = Θ(kn) и постоји c, такво да је m(n) = O(cn).

Информатичари обично сматрају да су алгоритми који захтевају полиномијално време брзи, а да су сви алгоритми који захтевају време дуже од полиномијалног спори (види Кобхамову тезу). По овој дефиницији, експоненцијално време би се стога сматрало спорим. Оваква класификација пружа корисну представу, али је непрецизна. У пракси, време које је алгоритму заиста потребно за извршавање зависи од величине улаза, n, и од константи (види нотација великог O за више детаља). За дати улаз n, неки полиномијални алгоритам може да има веће време извршавања него неки експоненцијални алгоритам. Међутим, за довољно велике вредности n, време извршавања експоненцијалног алгоритма ће постати веће.

Постоје алгоритми који захтевају више времена од полиномијалног времена (супер-полиномијално време) али мање од експоненцијалног времена (суб-експоненцијално време). Један такав пример је најбољи познати алгоритам за факторизацију целих бројева. Овакви алгоритми се такође сматрају спорим.

Честа је грешка да се квадратно време сматра експоненцијалним. Квадратно време се односи на специјални случај полиномијалног времена, код кога је највећи експонент једнак 2, на пример n2. Експоненцијално време подразумева да променљива стоји у експоненту, на пример 2n. Проблеми за чије решавање је потребно квадратно или полиномијално време, могу бити временски захтевни, али обично спадају у проблеме који се у пракси могу решити. (мада је и квадратно време понекад неприхватљиво када су у питању интерактивне апликације). За проблеме који захтевају експоненцијално време се сматра да у пракси нису решиви, изузев за мале улазне вредности.

Види још[уреди]