Algorytm wielomianowy – algorytm, którego czas działania ograniczony jest przez wielomian od rozmiaru danych wejściowych. Inaczej mówiąc jest to algorytm, którego czasowa złożoność obliczeniowa wynosi gdzie jest rozmiarem danych wejściowych, a pewną stałą niezależną od tego rozmiaru.
Problemy obliczeniowe, dla których istnieje algorytm wielomianowy, są przyjmowane za łatwo rozwiązywalne. Problemy, dla których nie jest znany algorytm wielomianowy (jak np. problemy NP-zupełne), określane są jako trudno rozwiązywalne.
Zobacz też algorytm pseudowielomianowy notacja dużego O problem NP problem NP-trudny
Przypisy
Kategoria:Teoria obliczeń