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 $O(n^k),$ gdzie $n$ jest rozmiarem danych wejściowych, a $k$ 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