Datenstrukturen - Grundlagen der Algorithmen
Der Algorithmus ist eine schrittweise Prozedur, die eine Reihe von Anweisungen definiert, die in einer bestimmten Reihenfolge ausgeführt werden müssen, um die gewünschte Ausgabe zu erhalten. Algorithmen werden im Allgemeinen unabhängig von den zugrunde liegenden Sprachen erstellt, dh ein Algorithmus kann in mehr als einer Programmiersprache implementiert werden.
Aus Sicht der Datenstruktur sind im Folgenden einige wichtige Kategorien von Algorithmen aufgeführt:
Search - Algorithmus zum Suchen eines Elements in einer Datenstruktur.
Sort - Algorithmus zum Sortieren von Elementen in einer bestimmten Reihenfolge.
Insert - Algorithmus zum Einfügen eines Elements in eine Datenstruktur.
Update - Algorithmus zum Aktualisieren eines vorhandenen Elements in einer Datenstruktur.
Delete - Algorithmus zum Löschen eines vorhandenen Elements aus einer Datenstruktur.
Eigenschaften eines Algorithmus
Nicht alle Prozeduren können als Algorithmus bezeichnet werden. Ein Algorithmus sollte die folgenden Eigenschaften haben:
Unambiguous- Der Algorithmus sollte klar und eindeutig sein. Jeder seiner Schritte (oder Phasen) und seine Ein- / Ausgänge sollten klar sein und dürfen nur zu einer Bedeutung führen.
Input - Ein Algorithmus sollte 0 oder mehr genau definierte Eingaben haben.
Output - Ein Algorithmus sollte 1 oder mehr genau definierte Ausgaben haben und mit der gewünschten Ausgabe übereinstimmen.
Finiteness - Algorithmen müssen nach einer endlichen Anzahl von Schritten beendet werden.
Feasibility - Sollte mit den verfügbaren Ressourcen machbar sein.
Independent - Ein Algorithmus sollte schrittweise Anweisungen haben, die unabhängig von Programmcode sein sollten.
Wie schreibe ich einen Algorithmus?
Es gibt keine genau definierten Standards für das Schreiben von Algorithmen. Es ist vielmehr problem- und ressourcenabhängig. Algorithmen werden niemals geschrieben, um einen bestimmten Programmiercode zu unterstützen.
Da wir wissen, dass alle Programmiersprachen grundlegende Codekonstrukte wie Schleifen (do, for, while), Flusskontrolle (if-else) usw. gemeinsam haben, können diese allgemeinen Konstrukte zum Schreiben eines Algorithmus verwendet werden.
Wir schreiben Algorithmen Schritt für Schritt, aber das ist nicht immer der Fall. Das Schreiben von Algorithmen ist ein Prozess und wird ausgeführt, nachdem die Problemdomäne genau definiert wurde. Das heißt, wir sollten die Problemdomäne kennen, für die wir eine Lösung entwerfen.
Beispiel
Lassen Sie uns anhand eines Beispiels versuchen, das Schreiben von Algorithmen zu lernen.
Problem - Entwerfen Sie einen Algorithmus, um zwei Zahlen hinzuzufügen und das Ergebnis anzuzeigen.
Step 1 − START
Step 2 − declare three integers a, b & c
Step 3 − define values of a & b
Step 4 − add values of a & b
Step 5 − store output of step 4 to c
Step 6 − print c
Step 7 − STOP
Algorithmen sagen den Programmierern, wie sie das Programm codieren sollen. Alternativ kann der Algorithmus wie folgt geschrieben werden:
Step 1 − START ADD
Step 2 − get values of a & b
Step 3 − c ← a + b
Step 4 − display c
Step 5 − STOP
Beim Entwurf und der Analyse von Algorithmen wird normalerweise die zweite Methode verwendet, um einen Algorithmus zu beschreiben. Dies erleichtert dem Analysten die Analyse des Algorithmus, wobei alle unerwünschten Definitionen ignoriert werden. Er kann beobachten, welche Operationen verwendet werden und wie der Prozess abläuft.
Schreiben step numbers, es ist optional.
Wir entwerfen einen Algorithmus, um eine Lösung für ein bestimmtes Problem zu erhalten. Ein Problem kann auf mehrere Arten gelöst werden.
Daher können viele Lösungsalgorithmen für ein gegebenes Problem abgeleitet werden. Der nächste Schritt besteht darin, diese vorgeschlagenen Lösungsalgorithmen zu analysieren und die am besten geeignete Lösung zu implementieren.
Algorithmusanalyse
Die Effizienz eines Algorithmus kann in zwei verschiedenen Phasen vor und nach der Implementierung analysiert werden. Sie sind die folgenden -
A Priori Analysis- Dies ist eine theoretische Analyse eines Algorithmus. Die Effizienz eines Algorithmus wird gemessen, indem angenommen wird, dass alle anderen Faktoren, beispielsweise die Prozessorgeschwindigkeit, konstant sind und keinen Einfluss auf die Implementierung haben.
A Posterior Analysis- Dies ist eine empirische Analyse eines Algorithmus. Der ausgewählte Algorithmus wird mit der Programmiersprache implementiert. Dies wird dann auf dem Zielcomputer ausgeführt. In dieser Analyse werden aktuelle Statistiken wie Laufzeit und Platzbedarf gesammelt.
Wir werden etwas über eine A-priori- Algorithmus-Analyse lernen . Die Algorithmusanalyse befasst sich mit der Ausführung oder Laufzeit verschiedener beteiligter Operationen. Die Laufzeit einer Operation kann als die Anzahl der pro Operation ausgeführten Computeranweisungen definiert werden.
Komplexität des Algorithmus
Annehmen X ist ein Algorithmus und n ist die Größe der Eingabedaten, die vom Algorithmus X verwendete Zeit und der Raum sind die beiden Hauptfaktoren, die die Effizienz von X bestimmen.
Time Factor - Die Zeit wird gemessen, indem die Anzahl der Schlüsseloperationen wie Vergleiche im Sortieralgorithmus gezählt wird.
Space Factor - Der Speicherplatz wird gemessen, indem der vom Algorithmus maximal benötigte Speicherplatz gezählt wird.
Die Komplexität eines Algorithmus f(n) gibt die Laufzeit und / oder den vom Algorithmus benötigten Speicherplatz in Bezug auf an n als Größe der Eingabedaten.
Raumkomplexität
Die Raumkomplexität eines Algorithmus repräsentiert die Menge an Speicherplatz, die der Algorithmus in seinem Lebenszyklus benötigt. Der von einem Algorithmus benötigte Platz entspricht der Summe der folgenden beiden Komponenten:
Ein fester Teil, der zum Speichern bestimmter Daten und Variablen erforderlich ist, die unabhängig von der Größe des Problems sind. Zum Beispiel verwendete einfache Variablen und Konstanten, Programmgröße usw.
Ein variabler Teil ist ein Platz, der von Variablen benötigt wird, deren Größe von der Größe des Problems abhängt. Zum Beispiel dynamische Speicherzuweisung, Rekursionsstapelspeicher usw.
Die Raumkomplexität S (P) eines beliebigen Algorithmus P ist S (P) = C + SP (I), wobei C der feste Teil und S (I) der variable Teil des Algorithmus ist, der von der Instanzcharakteristik I abhängt ist ein einfaches Beispiel, das versucht, das Konzept zu erklären -
Algorithm: SUM(A, B)
Step 1 - START
Step 2 - C ← A + B + 10
Step 3 - Stop
Hier haben wir drei Variablen A, B und C und eine Konstante. Daher ist S (P) = 1 + 3. Nun hängt der Raum von Datentypen gegebener Variablen und konstanter Typen ab und wird entsprechend multipliziert.
Zeitliche Komplexität
Die zeitliche Komplexität eines Algorithmus gibt die Zeit an, die der Algorithmus benötigt, um vollständig ausgeführt zu werden. Zeitanforderungen können als numerische Funktion T (n) definiert werden, wobei T (n) als Anzahl von Schritten gemessen werden kann, vorausgesetzt, jeder Schritt verbraucht konstante Zeit.
Zum Beispiel dauert das Hinzufügen von zwei n-Bit-Ganzzahlen nSchritte. Folglich ist die Gesamtberechnungszeit T (n) = c ≤ n, wobei c die Zeit ist, die für die Addition von zwei Bits benötigt wird. Hier beobachten wir, dass T (n) mit zunehmender Eingangsgröße linear wächst.