Üstel zaman

Vikipedi, özgür ansiklopedi

Üstel zamanda çalışan bir algoritma, bir Turing makinesinin girişin uzunluğunun en fazla e ^ { p( n ) } \, katı tane adımda çözebildiği bir problemdir (p, herhangi bir polinom olabilir). Doğal olarak, üstel zaman polinomsal zamanı içine alabilir.

Örneğin, seyyar satıcı problemini mümkün olan tüm turları teker teker hesaplayıp çözmek üstel zaman alacaktır, zira n \, şehir için n! \, tur vardır...

Ayrıca bakınız: Logaritmik zaman, Polinomsal zaman, NP-complete