Algorytm wielomianowy

Algorytm wielomianowy

Algorytm wielomianowy to taki, którego czas działania jest ograniczony przez wielomian w zależności od rozmiaru danych wejściowych. Można go opisać jako algorytm o czasowej złożoności obliczeniowej wynoszącej $O(n^k)$, gdzie $n$ to rozmiar danych wejściowych, a $k$ jest stałą niezależną od tego rozmiaru.

Problemy obliczeniowe, dla których istnieje algorytm wielomianowy, są uważane za łatwe do rozwiązania. Natomiast problemy, dla których nie ma znanego algorytmu wielomianowego, takie jak problemy NP-zupełne, klasyfikowane są jako trudne do rozwiązania.