Ziel
Du wirst verstehen warum Algorithmen analysiert werden und wie man das überhaupt berwerkstelligen kann. Du wirst verstehen warum es Schwierigkeiten beim Analysieren von Algorithmen gibt und wie diese intelligent beseitigt wurden. Außerdem wird dir klar werden wie man bei der Analyse vorgeht. Zu letzt wirst du Begriffe wie Random Access Machine, Komplexität und Worst Case kennen lernen.
Warum werden Algorithmen analysiert?
Dieser Spruch gilt auch für Algorithmen. Es gibt nämlich mehrere Möglichkeiten eine Menge aus Zahlen aufsteigend zu sortieren. Doch welcher Algorithmus erledigt die Aufgabe am schnellsten und Kostengünstigsten? Aus diesem Grund analysieren wir Algorithmen. Man nennt es auch Laufzeitanalysen.
Was ist eine Laufzeitanalyse?
Doch was genau machen wir bei einer Laufzeitanalyse? Ein Algorithmus besteht aus Operationen, z.b wird addiert, subtrahiert, multipliziert, dividiert usw. Jetzt können wir bereits sagen, dass eine Addition im Rechner schneller abläuft als eine Multiplikation, da eine Multiplikation eine wiederholte Addition darstellt. Wir benötigen also für unterschiedliche Operationen unterschiedlich viel Zeit. Der Speicher und Zeitbedarf eines Algorithmus hängt von einer zentralen Operation ab.
Wir könnten zwei Algorithmen vergleichen, welche die gleiche Aufgabe haben, indem wir sie laufen lassen und die Zeit stoppen. Jetzt ist das Problem aber, dass diese Vorgehensweise von mehreren Faktoren abhängig ist, die zu einer Verfälschung der Ergebnisse führen können.
Warum ist diese Vorgehensweise ein Problem?
Es kann sein dass es Zufall war, dass der eine Algorithmus mit der Eingabe besser zurecht kam.
Ein anderer Grund könnte sein, dass wir den Algorithmus auf unterschiedlichen Rechnern messen und aufgrund der unterschiedlichen Rechenleistung verfälschte Ergebnisse erhalten. Die Taktfrequenz eines Rechners spielt nämlich auch eine Rolle. Wie lange testen wir überhaupt und wie groß ist die Eingabefolge die unsere Algorithmen bearbeiten sollen, damit wir überhaupt einen nennenswerten Unterschied erkennen? Das heißt wir können uns nicht auf die absoluten Zeitwerte verlassen.
Wovon ist die Laufzeit abhängig?
Lassen wir den Algorithmus auf einem echten Rechner laufen(z.b deinen) dann ist die Laufzeit von mehreren Faktoren abhängig:
- Eingabegröße(Wie viele Zahlen sollen sortiert werden?)
- Struktur der Eingabe(Besteht die Eingabe z.b nur aus Zahlen?)
- Taktfrequenz(Wie leistungsstark ist der Rechner?)
- Speichergröße(Haben wir genug Speicherplatz zur Verfügung?)
- Programmiersprache(Ist der Code maschinennah oder nicht?)
- Implementierung (Viele Wege führen nach Rom und einige sind kürzer)
Wie können wir dennoch Algorithmen miteinander vergleichen?
Die Lösung für das Problem ist, von der physischen Implementierung des Algorithmus zu abstrahieren. Das heißt wir brauchen ein abstraktes Modell, welches die oben genannten Faktoren, welche unser Ergebnis verfälschen können eliminieren. Ein solches Modell ist die RAM(Random Access Machine) nicht zu verwechseln mit RAM(Random access Memory).
Was ist so eine Random Access Machine?
Eine Random Access Machine ist eine sogenannte Registermaschine. Es ist ein abstrahiertes Modell eines Rechners, auf dem unsere zu verrgleichenden Algorithmen rein theoretisch laufen würden. Ein solches Modell besteht nur aus den wesentlichen Komponenten die für das theoretische Ausführen von Algorithmen notwendig sind. Dadurch spielt die Taktfrequenz, Implementierung, Programmiersprache und Speichergröße für uns keine Rolle mehr. So ein RAM besteht im Grunde nur aus zwei (unendlich großen) Speichern und einem Programmierbaren CPU. Programmiert wird so ein RAM mit Pseudocode, wodurch er unabhängig von der Programmiersprache ist.
Ein Speicher ist für das Abspeichern der Programmanweisungen und der andere zum Speichern der Daten. Ein Programm, was so eine Registermaschine simuliert ist PhytEmu.
Übrig bleiben noch die Struktur der Eingabe und die Eingabegröße.Wir müssen irgendwie unsere Algorithmen miteinander vergleichen können. Wenn wir aber nicht die Zeit messen dürfen wie könnten wir dann erkennen welcher Algorithmus mehr Ressourcenbedarf benötigt?Dafür können wir uns anschauen wie komplex unsere Algorithmen sind und dann dessen Komplexität miteinander vergleichen.
Was ist Komplexität?
Unter der Komplexität […] eines Algorithmus […] versteht man in der Komplexitätstheorie seinen maximalen Ressourcenbedarf.“
– Wiki
Ein Algorithmus ist somit komplexer je mehr Speicherplatz, oder Rechenzeit er benötigt. Wie bereits erklärt, sollten wir die Laufzeit nicht direkt messen(z.b in Millisekunden) da es zu viele Faktoren gibt, die das Ergebnis verfälschen, also benötigen wir einen anderen Indikator, um die Algorithmen zu bewerten. Dafür eignen sich die Operationen des Algorithmus. Die Rechenzeit ist von den Operationen des Algorithmus(Addition, Multipliaktion… usw) abhängig. Wir können also sagen, je mehr Operationen statt finden, umso komplexer ist unser Algorithmus. Zunächst einmal müssen wir bestimmen wie viele Ressourcen bestimmte Operationen kosten.
| Beispiel | Operation | Zeiteinheiten |
|---|---|---|
a = 5 | Speichern/Laden | 0 |
a + b | Einfache Operationen Beim Vergleichen findet im Rechner eine Berechnung statt. Das lernst du in der technischen Informatik. | 1 |
Wir könnten jetzt einen Algorithmus auseinander nehmen und dann sagen wie viele Zeiteinheiten er jeweils benötigt und dann bewerten welcher schneller ist.
| Algorithmus | Zeiteinheiten | Erklärung |
|---|---|---|
variable = 42 | 0 | Speichern benötigt keine Ressourcen. |
ergebnis = a + b | 1 | Die einzige Operation ist die Addition, sie läuft genau einmal ab. |
c = a * b | 1 | Die Multiplikation läuft nach unserer Definition genau so schnell. Wir wollen keine Linsen spalten. |
for (i to 4) { | 4 | Die Schleife läuft 4 mal und es wird 4 mal addiert. |
Der letzte Algorithmus ist der mit dem größten Ressourcenbedarf, aber spielt es überhaupt eine Rolle ob ein Algorithmus ein paar Zeiteinheiten schneller ist als ein anderer? In der Praxis ist es nicht entscheidend ob ein Algorithmus 4 Millisekunden schneller ist, weil er vier Additionen weniger berechnen muss. Deswegen vereinfachen wir die Operationen in dem wir die Rechenoperationen und Vergleichsoperationen(welche praktisch ebenfalls Rechenoperationen sind) zusammenfassen. Das reicht aber noch nicht aus, denn es könnte ja auch sein, dass die Anzahl der Rechenoperationen mit der Eingabe anwächst. Zum Beispiel ein Algorithmus der eine Folge an Zahlen sortieren soll. Je mehr Zahlen er als Eingabe erhält, umso mehr Rechenoperationen müssen durchgeführt werden.
Wir müssen uns die Frage stellen: Wie verhält sich die Anzahl der durchgeführten Operationen in unserem Algorithmus, in Abhängigkeit zur Eingabegröße?
Abhängigkeit von der Eingabegröße
Haben wir einen einfachen Algorithmus in der eine Summe berechnet wird…
summe(a,b){
ergebnis = a + b;
return ergebnis;
}…so können wir sagen, dass die Anzahl der Rechenoperationen nicht von der Eingabe abhängig ist. Der Algorithmus läuft immer nur einmal ab. Egal wie groß a oder b ist.
Ein Algorithmus der einen String verarbeitet und zurückgibt wie oft der Buchstabe F darin vorkommt könnte so aussehen:
Links befindet sich der Code des Algorithmus, aufgeteilt in seine Zeilen.
| Algorithmus | Ressourcen | Erklärung |
f = 0; | 0 | Speichern benötigt keine Zeiteinheiten |
for zeichen in satz { | n * 1 = n | Je mehr Zeichen umso öfter läuft die Schleife |
if zeichen == 'F' { | n * 1 = n | Mit jedem Schleifendurchgang wird verglichen |
dann f = f + 1; | c * 1 = c | Konstant, weil unabhängig von Eingabe |
}} | Rechenzeit: 2n + c |
Hier können wir sehen, je länger unser Satz ist, umso öfters läuft die Schleife. Die Laufzeit des Algorithmus ist von der Länge des Strings abhängig, man sagt auch von ‘n’ abhängig. ‘n’ wird in der Regel als Eingabe definiert.
Worst Case
Unter der Komplexität […] eines Algorithmus […] versteht man in der Komplexitätstheorie seinen maximalen Ressourcenbedarf.“
– Wiki
In dieser Definition taucht noch der Begriff “maximaler Ressourcenbedarf” auf. Man bezeichnet ihn auch als Worst-Case. Würden wir den Algorithmus von oben unter der Maximalen Laufzeit anschauen, dann wäre das ein String der nur aus dem gesuchten Buchstaben besteht.
satz = "FFFFFFFFFFFFFFFFFFFFFFFFFFFF";
f = 0;
for zeichen in satz{
if zeichen == 'F' {
dann f = f + 1;
}
}Das würde dazu führen, dass unsere Konstante c sich proportional zu der Länge des Strings(n) verhält. Dadurch erhalten wir eine Rechenzeit von: 2n + n = 3n. Oder anders ausgedrückt. Unsere Zeile f = f + 1, müsste somit nicht mehr nur dann ausgeführt werden wenn ein F im String vorkommt, sondern mit jedem Durchgang. Immerhin besteht der gesamte String nur aus diesem Zeichen.
Warum nimmt man zur Bestimmung der Komplexität den Worst-Case?
Dazu gibt es mehrere Gründe, einerseits taucht der Worst Case in der Realität sehr häufig auf. Bei dem Durchsuchen einer Datenbank würde eine Suche nach einem nicht existierenden Datensatz dazu führen, dass er die gesamte Datenbank durchsucht. Der Algorithmus verursacht also seinen maximalen Ressourcenbedarf. Ein anderer Grund ist, dass man häufig gar nicht sagen kann was man als Average Case nehmen soll und der Worst-Case leichter zu bestimmen ist. Der letzte und wichtigste Grund den Worst-Case zu nehmen ist es die Struktur der Eingabe zu eliminieren. Was dazu führt, dass nur noch ein Faktor übrig ist, der die Laufzeit beeinflusst und zwar die Eingabegröße. Somit haben wir nun die Möglichkeit verschiedene Algorithmen unter den gleichen Bedingungen zu vergleichen.
Begriffe
| Begriffe | Erklärung |
| Laufzeit/Rechenzeit | Anzahl der durchgeführten Elementaroperationen in Abhängigkeit von der Eingabegröße. Quelle |
| Laufzeitanalyse | Bei der Laufzeitanalyse wollen wir vergleichen, wie sich Algorithmen verhalten, wenn die Eingabegröße wächst. |
| Speicherplatz | Maximale Speicherverbrauch während der Ausführung des Algorithmus in Abhängigkeit von der Komplexität der Eingabe. Quelle |
| Komplexitätsanalyse | Mathematische Analyse, um eine Funktion in Abhängigkeit der Eingabegröße zu finden. Quelle |
| Komplexität | Eine Funktion in Abhängigkeit von einer Eingabelänge n. |
| Worst-Case-Rechenzeit | “die maximale Rechenzeit eines Algorithmus auf Eingaben der gleichen Länge, bei randomisierten Algorithmen (randomisierter Algorithmus) auch die maximale average case-Rechenzeit.” Quelle |
Hat dir der Inhalt gefallen?
Falls du mehr zu Themen der Informatik lesen willst, kannst du die Suche dafür verwenden:
Du bist der Meinung, das war der Beste Beitrag zum Thema Informatik den du jemals gelesen hast? Dann ist die einzig logische Schlussfolgerung, diesen Beitrag mit deinen Kommilitonen zu teilen. Oder auch nicht mach was du willst, ich bin nicht dein Dad.