Aufwand und Effizienz


Eines der Kriterien zur Beurteilung eines Algorithmus, und keineswegs immer das wichtigste, ist die Frage nach dem Aufwand (gemessen in einem geeigneten Maß) für die Lösung eines gegebenen Problems. Andere Eigenschaften wie Einfachheit, Klarheit und Verständlichkeit, Wartbarkeit und Änderbarkeit, Übertragbarkeit und Anpaßbarkeit, Robustheit und Fehlertoleranz (und natürlich die Korrektheit!) sind oft weitaus bedeutsamer. Von Interesse ist der Aufwand oder die Effizienz dann, wenn die bei konkretem Einsatz entstehenden Kosten nicht vernachlässigbar oder gar unerträglich hoch sind.

Im Einzelfall wird man den Aufwand einfach messen,  aber um für weitere Einsätze eine Vorhersage machen zu können, sollte man etwas über die Abhängigkeit des Aufwandes von der Problemgröße wissen, zumal dann, wenn mehrere Verfahren zur Auswahl stehen. Man wird also versuchen, den Aufwand zu berechnen. Dies kann sehr detailliert geschehen und ist dann oft sehr schwierig; oft genügen aber schon globale Aussagen der Art, wie stark der Aufwand mit der Problemgröße wächst, und sie sind oft recht einfach zu erhalten. Eine solche asymptotische Abschätzung ist recht grob und nur bis auf einen konstanten Faktor bekannt, dennoch kann sie zur Auswahl eines geeigneten Verfahrens ausreichen.

Um über das Wachstumsverhalten von Funktionen reden zu können, definieren wir:

Die Größenordnung einer Funktion f: NN ist die Menge der Funktionen g, die schließlich nicht schneller anwachsen  als f:

(f) = { g: NN | c>0 n0 mit g(n) <= c*f(n) n >= n0 }

f(n) ist also für genügend große n bis auf einen konstanten Faktor c eine obere Schranke  für g(n).

Für g(f) sagt man gerne: g(n) ist von der Größenordnung  f(n). Gebräuchlich sind auch die Sprechweisen:
Inhalt | Index | vor | Vorlesung

Klaus Lagally, 22. Februar 2000, 19:36