Effizienz (Algorithmus)

Die Effizienz eines Algorithmus bestimmt sich mehrere spezielle Effizienz-Kriterien:

• Laufzeiteffizienz
• Speichereffizienz
• Kognitive Effizenz : Verständlichkeit und Natürlichkeit der Implementierung . Da man diese Eigenschaft nicht in fassen kann wird sie bei der Bestimmmung Gesamt-Effizienz eines Algorithmus oft nicht berücksichtigt.

Laufzeit- und Speichereffizienz sind nicht alleine Eigenschaft des Algorithmus sondern werden auch von konkreten Implementation der zugrundeliegenden Hardware sowie von konkreten Eingabedaten beeinflusst. Erstrebt wird jedoch eine die unabhängig von diesen Faktoren ist. Dies erreicht indem man

• die Laufzeit eines Algorithmus nicht anhand der Dauer bestimmt sondern die benötigten Rechenschritte ermittelt dabei jede Art der Anweisung (Addition Multiplikation Schleife ...) verschieden bewertet wird
• sowie anhand des tatsächlichen Speicherbedarfs (in Byte ) eine Anzahl von Speicherplätzen unbestimmter Größe die Variablen berechnet.

Der Begriff effizienter Algorithmus wird in der theoretischen Informatik recht schwammig benutzt. Meist meint man einen Algorithmus dessen Laufzeit polynomial in der der Eingabe ist aber auch solche Algorithmen praktisch unbrauchbar sein wenn beispielsweise der feste <math>k</math> des zugehörigen Polynoms <math>n^k</math> zu groß Es gibt sogar Linearzeit-Algorithmen die praktisch unbrauchbar weil der konstante Vorfaktor <math>c</math> in der <math>c\cdot n</math> zu groß ist.

Bücher zum Thema Effizienz (Algorithmus)

Dieser Artikel von Wikipedia unterliegt der GNU FDL.