Analyse und Effizienz von Algorithmen

Es gibt mehrere Möglichkeiten, ein Problem zu lösen. Wie können wir zwischen ihnen wählen?

Ziele bei der Gestaltung von Computerprogrammen

Generell gibt es zwei Ziele bei der Gestaltung von Computerprogrammen:

• Die Konstruktion eines Algorithmus, der leicht zu verstehen ist, sowie dessen Kodifizierung und Debugging (Software Engineering).
• Die Konstruktion eines Algorithmus, der Computer-Ressourcen effizient nutzt (Analyse und Entwurf von Algorithmen).

Die Analyse von Algorithmen ermöglicht es uns, die Schwierigkeit eines Problems zu messen und die Effizienz eines Algorithmus zu bewerten.

Messung der Ausführungszeit

Man kann die Zeit nicht in Sekunden messen, da es keinen Standard-Referenzcomputer gibt. Stattdessen misst man die Zahl der grundlegenden oder elementaren Operationen.

Die grundlegenden Operationen werden vom Computer in konstanter Zeit ausgeführt, z. B.:

• Grundrechenarten
• Zuweisung vordefinierter Typen
• Sprünge (Aufrufe von Funktionen, Prozeduren und Rücksprünge)
• Logische Vergleiche
• Indizierter Zugriff auf Grundstrukturen (Vektoren und Matrizen)

Es ist möglich, die Komplexität eines Algorithmus zu untersuchen, indem man sich nur auf eine kleine Menge von Operationen konzentriert, die die Laufzeit beeinflussen.

Methoden zur Messung der Ausführungszeit

Zur Messung der Ausführungszeit eines Algorithmus gibt es mehrere Methoden. Einige davon sind:

Benchmarking

Die Benchmark-Methode betrachtet eine Sammlung von Eingaben, die einer typischen Auslastung für ein Programm entsprechen.

Profiling

Beim Profiling wird jeder Anweisung eines Programms eine Zahl zugeordnet, die den Anteil der gesamten Ausführungszeit für diese Anweisung darstellt. Eine der bekanntesten (und informellen) Techniken ist die 90-10-Regel, die besagt, dass 90 % der Ausführungszeit auf 10 % des Codes entfallen.

Analyse

Bei der Analyse werden Eingaben nach ihrer Größe gruppiert, und die Ausführungszeit des Programms für Eingaben dieser Größe, T(n), wird geschätzt. Dies ist die Technik, die im Folgenden untersucht wird.

Die Ausführungszeit kann somit als Funktion der Eingabegröße definiert werden. T(n) bezeichnet die Laufzeit eines Algorithmus für eine Eingabe der Größe n.

Asymptotische Analyse

Der Schwerpunkt der Analyse von Algorithmen liegt darin, wie die Ausführungszeit wächst, wenn die Größe der Eingabe zunimmt. Dies ist die asymptotische Effizienz des Algorithmus. Sie wird als "asymptotisch" bezeichnet, weil sie das Verhalten von Funktionen im Grenzfall, d. h. die Wachstumsrate, analysiert.

Asymptotische Notation wird verwendet, um die Laufzeit oder den Speicherplatz von Algorithmen in Abhängigkeit von der Länge der Eingabe zu beschreiben. Sie wird durch eine Funktion geschätzt, deren Definitionsbereich die natürlichen Zahlen (N) sind. Es handelt sich um asymptotisch nichtnegative Funktionen.

Asymptotische Notation erfasst das Verhalten der Funktion für große Werte von N.

Die Notationen sind nicht von den zuvor betrachteten Fällen abhängig. Daher ist eine Notation, die den Worst Case bestimmt, in jeder Situation relevant.