Datenstrukturen-Algorithmen Grundlagen

Der Algorithmus ist eine Schritt-für-Schritt-Prozedur, die eine Reihe von Anweisungen definiert, die in einer bestimmten Reihenfolge ausgeführt werden sollen, um die gewünschte Ausgabe zu erhalten. Algorithmen werden im Allgemeinen unabhängig von zugrunde liegenden Sprachen erstellt, dh ein Algorithmus kann in mehr als einer Programmiersprache implementiert werden.,

Aus Sicht der Datenstruktur folgen einige wichtige Kategorien von Algorithmen –

• Search-Algorithmus zum Suchen eines Elements in einer Datenstruktur.

• Sortieren-Algorithmus zum Sortieren von Elementen in einer bestimmten Reihenfolge.

• Insert-Algorithmus zum Einfügen von Elementen in eine Datenstruktur.

• Update-Algorithmus zum Aktualisieren eines vorhandenen Elements in einer Datenstruktur.

• Delete − Algorithmus zum löschen eines vorhandenen Elements aus der Datenstruktur.

Eigenschaften eines Algorithmus

Nicht alle Prozeduren können als Algorithmus bezeichnet werden., Ein Algorithmus sollte die folgenden Eigenschaften haben –

• Eindeutig-Algorithmus sollte klar und eindeutig sein. Jeder seiner Schritte (oder Phasen) und ihre Ein – /Ausgänge sollten klar sein und müssen nur zu einer Bedeutung führen.

• Eingabe – Ein Algorithmus sollte 0 oder mehr gut definierte Eingaben haben.

• Ausgabe – Ein Algorithmus sollte 1 oder mehr genau definierte Ausgänge haben und mit der gewünschten Ausgabe übereinstimmen.

• Endlichkeit-Algorithmen müssen nach einer endlichen Anzahl von Schritten beendet werden.,

• Machbarkeit-Sollte mit den verfügbaren Ressourcen machbar sein.

• Unabhängig-Ein Algorithmus sollte Schritt-für-Schritt-Anweisungen haben, die von jedem Programmiercode unabhängig sein sollten.

Wie schreibe ich einen Algorithmus?

Es gibt keine genau definierten Standards für das Schreiben von Algorithmen. Vielmehr ist es problem – und ressourcenabhängig. Algorithmen werden niemals geschrieben, um einen bestimmten Programmiercode zu unterstützen.

Wie wir wissen, teilen sich alle Programmiersprachen grundlegende Codekonstrukte wie Schleifen (do, for, while), Flusskontrolle (if-else) usw., Diese gemeinsamen Konstrukte können verwendet werden, um einen Algorithmus zu schreiben.

Wir schreiben Algorithmen Schritt für Schritt, aber das ist nicht immer der Fall. Algorithm Writing ist ein Prozess und wird ausgeführt, nachdem die Problemdomäne gut definiert ist. Das heißt, wir sollten die Problemdomäne kennen, für die wir eine Lösung entwerfen.

Beispiel

Let“s versuchen zu lernen, algorithmen zu schreiben, indem Sie sich mit einem Beispiel.

Problem-Entwerfen Sie einen Algorithmus, um zwei Zahlen hinzuzufügen und das Ergebnis anzuzeigen.

Step 1 − STARTStep 2 − declare three integers a, b & cStep 3 − define values of a & bStep 4 − add values of a & bStep 5 − store output of step 4 to cStep 6 − print cStep 7 − STOP

Algorithmen sagen den Programmierern, wie das Programm zu codieren., Alternativ kann der Algorithmus als −

Step 1 − START ADDStep 2 − get values of a & bStep 3 − c ← a + bStep 4 − display cStep 5 − STOP

In Design und Analyse von Algorithmen geschrieben werden, üblicherweise wird die zweite Methode verwendet, um einen Algorithmus zu beschreiben. Es macht es dem Analytiker leicht, den Algorithmus zu analysieren, der alle unerwünschten Definitionen ignoriert. Er kann beobachten, welche Operationen verwendet werden und wie der Prozess fließt.

Schreiben Schritt zahlen, ist optional.

Wir entwerfen einen Algorithmus, um eine Lösung für ein bestimmtes Problem zu erhalten. Ein Problem kann auf mehr als eine Weise gelöst werden.,

Daher können viele Lösungsalgorithmen für ein bestimmtes 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 vor und nach der Implementierung in zwei verschiedenen Phasen analysiert werden. Sie sind die folgenden −

• A-Priori-Analyse − Dies ist eine theoretische Analyse des 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.

• Eine posteriore Analyse-Dies ist eine empirische Analyse eines Algorithmus. Der ausgewählte Algorithmus wird mithilfe der Programmiersprache implementiert. Dies wird dann auf dem Zielcomputer ausgeführt. In dieser Analyse werden aktuelle Statistiken wie Laufzeit und Platzbedarf erfasst.

Wir werden über a priori Algorithmus Analyse lernen., Die Algorithmusanalyse befasst sich mit der Ausführung oder Laufzeit verschiedener Vorgänge. Die Laufzeit einer Operation kann als die Anzahl der Computeranweisungen definiert werden, die pro Operation ausgeführt werden.

Komplexität des Algorithmus

Angenommen, 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

• Zeitfaktor-Die Zeit wird durch Zählen der Anzahl der Schlüsseloperationen wie Vergleiche im Sortieralgorithmus gemessen.,

• Raumfaktor-Der Raum wird durch Zählen des maximalen Speicherplatzes gemessen, der vom Algorithmus benötigt wird.

Die Komplexität eines Algorithmus f (n) gibt die Laufzeit und/oder den vom Algorithmus benötigten Speicherplatz in Bezug auf n als Größe der Eingabedaten an.

Raumkomplexität

Raumkomplexität eines Algorithmus stellt die Menge an Speicherplatz dar, die der Algorithmus in seinem Lebenszyklus benötigt., Der von einem Algorithmus benötigte Speicherplatz entspricht der Summe der folgenden zwei 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 werden einfache Variablen und Konstanten verwendet, Programmgröße usw.

• Ein Variablenteil ist ein Platz, der von Variablen benötigt wird, deren Größe von der Größe des Problems abhängt. Zum Beispiel dynamische Speicherzuweisung,Rekursionsstapel usw.,

Raumkomplexität S(P) eines 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.Es folgt ein einfaches Beispiel, das versucht, das Konzept zu erklären −

Algorithm: SUM(A, B)Step 1 - STARTStep 2 - C ← A + B + 10Step 3 - Stop

Hier haben wir drei Variablen A, B, und C und eine Konstante. Daher ist S(P) = 1 + 3. Der Speicherplatz hängt nun von den Datentypen der angegebenen Variablen und konstanten Typen ab und wird entsprechend multipliziert.,

Zeit Komplexität

Zeit Komplexität eines Algorithmus stellt die Menge an Zeit benötigt, die vom Algorithmus bis zum Abschluss. Zeitbedarf kann als numerische Funktion T(n) definiert werden, wobei T(n) als die Anzahl der Schritte gemessen werden kann, vorausgesetzt, jeder Schritt verbraucht konstante Zeit.

Das Hinzufügen von zwei N-Bit-Ganzzahlen dauert beispielsweise n Schritte. Folglich ist die gesamte Rechenzeit 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) linear wächst, wenn die Eingabegröße zunimmt.,