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^[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ż

Przypisy

↑ ^a ^b Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Wprowadzenie do algorytmów. Wyd. VII. Wydawnictwo Naukowe PWN, 2012, s. 1073. ISBN 978-83-01-16911-4.
↑ Michał Knasiecki: Wprowadzenie do NP-zupełności. [w:] Algorytm.org [on-line]. 1 sierpnia 2005. [dostęp 2021-05-22].

[wprowadzenie-1] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Wprowadzenie do algorytmów. Wyd. VII. Wydawnictwo Naukowe PWN, 2012, s. 1073. ISBN 978-83-01-16911-4.

[2] Michał Knasiecki: Wprowadzenie do NP-zupełności. [w:] Algorytm.org [on-line]. 1 sierpnia 2005. [dostęp 2021-05-22].

[1]

[2]