DAA - Analyse von Algorithmen
Bei der theoretischen Analyse von Algorithmen ist es üblich, ihre Komplexität im asymptotischen Sinne zu schätzen, dh die Komplexitätsfunktion für beliebig große Eingaben zu schätzen. Der Begriff"analysis of algorithms" wurde von Donald Knuth geprägt.
Die Algorithmusanalyse ist ein wichtiger Teil der Theorie der rechnerischen Komplexität, die eine theoretische Schätzung der erforderlichen Ressourcen eines Algorithmus zur Lösung eines bestimmten Rechenproblems liefert. Die meisten Algorithmen arbeiten mit Eingaben beliebiger Länge. Die Analyse von Algorithmen ist die Bestimmung der Menge an Zeit- und Raumressourcen, die zur Ausführung erforderlich sind.
Normalerweise wird die Effizienz oder Laufzeit eines Algorithmus als eine Funktion angegeben, die die Eingangslänge mit der Anzahl der Schritte in Beziehung setzt, bekannt als time complexityoder Speichervolumen, bekannt als space complexity.
Die Notwendigkeit der Analyse
In diesem Kapitel werden wir die Notwendigkeit der Analyse von Algorithmen und die Auswahl eines besseren Algorithmus für ein bestimmtes Problem erörtern, da ein Rechenproblem durch verschiedene Algorithmen gelöst werden kann.
Indem wir einen Algorithmus für ein bestimmtes Problem betrachten, können wir beginnen, die Mustererkennung zu entwickeln, damit ähnliche Arten von Problemen mit Hilfe dieses Algorithmus gelöst werden können.
Algorithmen unterscheiden sich oft stark voneinander, obwohl das Ziel dieser Algorithmen dasselbe ist. Zum Beispiel wissen wir, dass eine Reihe von Zahlen mit verschiedenen Algorithmen sortiert werden kann. Die Anzahl der von einem Algorithmus durchgeführten Vergleiche kann für dieselbe Eingabe mit anderen variieren. Daher kann die zeitliche Komplexität dieser Algorithmen unterschiedlich sein. Gleichzeitig müssen wir den von jedem Algorithmus benötigten Speicherplatz berechnen.
Die Analyse des Algorithmus ist der Prozess der Analyse der Fähigkeit zur Problemlösung des Algorithmus in Bezug auf die erforderliche Zeit und Größe (die Größe des Speichers für die Speicherung während der Implementierung). Das Hauptanliegen der Analyse von Algorithmen ist jedoch die erforderliche Zeit oder Leistung. Im Allgemeinen führen wir die folgenden Analysetypen durch:
Worst-case - Die maximale Anzahl von Schritten, die für eine Instanz der Größe ausgeführt werden a.
Best-case - Die Mindestanzahl von Schritten, die für eine Instanz der Größe ausgeführt werden a.
Average case - Eine durchschnittliche Anzahl von Schritten, die für eine Instanz der Größe ausgeführt wurden a.
Amortized - Eine Folge von Operationen, die auf die Eingabe der Größe angewendet werden a gemittelt über die Zeit.
Um ein Problem zu lösen, müssen wir sowohl die Zeit- als auch die Raumkomplexität berücksichtigen, da das Programm möglicherweise auf einem System ausgeführt wird, auf dem der Speicher begrenzt ist, aber ausreichend Speicherplatz verfügbar ist, oder umgekehrt. In diesem Zusammenhang, wenn wir vergleichenbubble sort und merge sort. Die Blasensortierung erfordert keinen zusätzlichen Speicher, die Zusammenführungssortierung erfordert jedoch zusätzlichen Speicherplatz. Obwohl die zeitliche Komplexität der Blasensortierung im Vergleich zur Zusammenführungssortierung höher ist, müssen wir möglicherweise die Blasensortierung anwenden, wenn das Programm in einer Umgebung ausgeführt werden muss, in der der Speicher sehr begrenzt ist.