Algorytm wykładniczy
W teorii złożoności obliczeniowej, algorytm wykładniczy to algorytm, którego czas działania T mierzony w zależności od rozmiaru danych wejściowych n określa funkcja wykładnicza (czyli każde zwiększenie danych o stałą wielkość powoduje pomnożenie czasu działania przez stały czynnik).
W zapisie matematycznym, oznacza to, że istnieje k > 1 takie że T(n)=Θ( kn).
Algorytmy wykładnicze nazywane są nieefektywnymi, w przeciwieństwie do algorytmów wielomianowych. Nie oznacza to, że algorytmy takie zawsze są wolniejsze od wielomianowych: dla małych danych mogą być nawet szybsze. Są jednak bardzo czułe na wielkość danych i dla wystarczająco dużych n działają zawsze wolniej niż wielomianowe.
Przykładem problemów, dla których najefektywniejsze znane rozwiązania są wykładnicze są problemy NP-zupełne.
Istnieją algorytmy działające w czasie tzw. "podwykładniczym", czyli mniejszym niż czas wykładniczy, ale większym niż dowolny czas wielomianowy. Przykładem takiego algorytmu jest GNFS służący do faktoryzacji dużych liczb.
