Polynomieller Algorithmus
Ein polynomieller Algorithmus ist ein Algorithmus, für den die Rechenzeit für die Lösung eines gegebenen Problems 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² ein Polynom ist - ein polynomieller Algorithmus.
Ein Algorithmus, der für eine Aufgabe beispielsweise 2n so lange benötigt, wächst nicht polynomiell, sondern exponentiell (siehe exponentieller Algorithmus). Dies möchte man in der Regel vermeiden.