Algorytmy wykładnicze w teorii złożoności obliczeniowej
W kontekście teorii złożoności obliczeniowej, algorytm wykładniczy to taki, którego czas wykonania T, zależny od rozmiaru danych wejściowych n, można opisać za pomocą funkcji wykładniczej. Oznacza to, że każde zwiększenie rozmiaru danych o stałą wartość prowadzi do pomnożenia czasu działania przez stały współczynnik.
Matematycznie, można to zapisać jako istnienie k > 1, dla którego T(n) = Θ(kn).
Algorytmy wykładnicze są klasyfikowane jako nieefektywne, w przeciwieństwie do algorytmów wielomianowych. Nie oznacza to jednak, że algorytmy te zawsze działają wolniej od algorytmów wielomianowych; dla niewielkich zbiorów danych mogą być nawet szybsze. Są one jednak bardzo wrażliwe na rozmiar danych i dla wystarczająco dużych wartości n zawsze działają wolniej niż algorytmy o czasie wielomianowym.
Przykładami problemów, dla których znane najszybsze rozwiązania są wykładnicze, są problemy NP-zupełne.
Istnieją również algorytmy, które działają w czasie określanym jako „podwykładniczy”, co oznacza, że ich czas wykonania jest mniejszy niż czas wykładniczy, lecz większy niż jakikolwiek czas wielomianowy. Przykładem takiego algorytmu jest GNFS, który służy do faktoryzacji dużych liczb.
