Експоненцијално време — разлика између измена
Садржај обрисан Садржај додат
м Бот: Селим 7 међујезичких веза, које су сад на Википодацима на d:q11167512 |
м Бот: исправљена преусмерења |
||
Ред 5:
Информатичари обично сматрају да су алгоритми који захтевају [[полиномијално време]] ''брзи'', а да су сви алгоритми који захтевају време дуже од полиномијалног ''спори'' (види [[Кобхамова теза|Кобхамову тезу]]). По овој дефиницији, експоненцијално време би се стога сматрало спорим. Оваква класификација пружа корисну представу, али је непрецизна. У пракси, време које је алгоритму заиста потребно за извршавање зависи од величине улаза, -{''n''}-, и од [[константа|константи]] (види [[нотација великог O]] за више детаља). За дати улаз -{''n''}-, неки полиномијални алгоритам може да има веће време извршавања него неки експоненцијални алгоритам. Међутим, за ''довољно велике'' вредности -{''n''}-, [[време извршавања]] [[експоненеијални алгоритам|експоненцијалног алгоритма]] ће постати веће.
Постоје алгоритми који захтевају више времена од [[полиномијално време|полиномијалног времена]] (''[[субекспоненцијално време|супер-полиномијално време]]'') али мање од експоненцијалног времена (''[[субекспоненцијално време|суб-експоненцијално време]]''). Један такав пример је најбољи познати алгоритам за [[факторизација целих бројева|факторизацију целих бројева]]. Овакви алгоритми се такође сматрају ''спорим''.
Честа је грешка да се [[квадратно време]] сматра експоненцијалним. Квадратно време се односи на специјални случај полиномијалног времена, код кога је највећи експонент једнак 2, на пример -{''n''<sup>2</sup>}-. Експоненцијално време подразумева да [[променљива]] стоји у [[експонент]]у, на пример -{2<sup>''n''</sup>}-. Проблеми за чије решавање је потребно квадратно или полиномијално време, могу бити временски захтевни, али ''обично'' спадају у проблеме који се у пракси могу решити. (мада је и [[квадратно време]] понекад неприхватљиво када су у питању интерактивне апликације). За проблеме који захтевају експоненцијално време се сматра да у пракси нису решиви, изузев за мале улазне вредности.
Ред 16:
*[[Нотација великог O]]
*[[Квантни рачунар]]
*[[НП-комплетни проблеми|НП-комплетност]]
[[Категорија:Теорија комплексности]]
| |||