Polynomieller Algorithmus

Ein polynomieller Algorithmus ist ein Algorithmus, für den die Rechenzeit für die Lösung eines gegebenen Problems in maximal polynomiell von der Problemgröße abhängt. Die Problemgröße bezieht sich dabei in der Regel auf die Eingabelänge.

Beispiel: Ein Sortieralgorithmus, der für ein doppelt so großes Array konsistent etwa viermal so lange benötigt (allgemeiner: der für ein n-mal so großes Array n²-mal so lange braucht), ist ein quadratischer und somit - weil n^2 ein Polynom ist - ein polynomieller Algorithmus.

Ein Algorithmus, der für eine Aufgabe beispielsweise $2^{n}$ benötigt, wächst nicht polynomiell, sondern exponentiell. Dies möchte man in der Regel vermeiden.