Was bedeutet polynomielle Laufzeit in der Informatik?
2 Antworten
Polynominelle Laufzeit bedeutet das die Laufzeit durch ein Polynom bestimmt wird, z.B. O(n^k) für irgendein k und die Eingabegröße n.
Also z.B. Quadratische Laufzeit O(n^2)
für n=10 wäre das dann 100 (Zeiteinheiten), für n = 20 schon 400 etc.
aber das ist noch besser als exponentielle Laufzeit: z.B. O(2^n)
da ist für n=10 1024, für n=20 dann 1,048,576.
Daher ist ein Algorithmus mit polynomineller Laufzeit effektiver als einer mit exponentieller Laufzeit.
Am schönsten wäre natürlich lineare Laufzeit O(n) oder stetige Laufzeit z.B. O(2) aber das ist nur selten realisierbar für beliebig große Eingaben.
O(N^k) für irgendein k. Nicht polynomiell ist zum Beispiel O(a^N), das wäre exponentiell, also stärker wachsend.
Die Laufzeit gibt an, wie schnell die Laufzeit mit der Größe des Problems steigt. Zum Beispiel:
Lineare Laufzeit O(N) meint, dass wenn ich die Größe des Problems N verdopple meine Laufzeit sich auch verdoppelt.
Quadratische Laufzeit O(N^2) meint, dass wenn ich N verdopple sich die Laufzeit vervierfacht.
Das ist nur eine ganz grobe Erklärung, eigentlich ist es ein wenig komplizierter: https://de.wikipedia.org/wiki/Landau-Symbole
Aber was ist dann eine polynomielle Laufzeit? :o