Algorytm wielomianowy
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[1][2].
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[1].
Zobacz też
- algorytm pseudowielomianowy
- notacja dużego O
- problem NP
- problem NP-trudny