Paralleler Algorithmus - Analyse
Die Analyse eines Algorithmus hilft uns festzustellen, ob der Algorithmus nützlich ist oder nicht. Im Allgemeinen wird ein Algorithmus basierend auf seiner Ausführungszeit analysiert(Time Complexity) und die Menge an Platz (Space Complexity) Es benötigt.
Da wir hoch entwickelte Speichergeräte zu angemessenen Kosten zur Verfügung haben, ist Speicherplatz kein Problem mehr. Daher wird der Raumkomplexität nicht so viel Bedeutung beigemessen.
Parallele Algorithmen sollen die Rechengeschwindigkeit eines Computers verbessern. Für die Analyse eines parallelen Algorithmus berücksichtigen wir normalerweise die folgenden Parameter:
- Zeitkomplexität (Ausführungszeit),
- Gesamtzahl der verwendeten Prozessoren und
- Gesamtkosten.
Zeitliche Komplexität
Der Hauptgrund für die Entwicklung paralleler Algorithmen war die Reduzierung der Rechenzeit eines Algorithmus. Daher ist die Bewertung der Ausführungszeit eines Algorithmus für die Analyse seiner Effizienz äußerst wichtig.
Die Ausführungszeit wird auf der Grundlage der Zeit gemessen, die der Algorithmus zur Lösung eines Problems benötigt. Die Gesamtausführungszeit wird vom Zeitpunkt der Ausführung des Algorithmus bis zum Stopp berechnet. Wenn nicht alle Prozessoren gleichzeitig die Ausführung starten oder beenden, ist die Gesamtausführungszeit des Algorithmus der Moment, in dem der erste Prozessor seine Ausführung gestartet hat, bis zu dem Moment, in dem der letzte Prozessor seine Ausführung beendet.
Die zeitliche Komplexität eines Algorithmus kann in drei Kategorien eingeteilt werden
Worst-case complexity - Wenn ein Algorithmus für eine bestimmte Eingabe Zeit benötigt maximum.
Average-case complexity - Wenn ein Algorithmus für eine bestimmte Eingabe Zeit benötigt average.
Best-case complexity - Wenn ein Algorithmus für eine bestimmte Eingabe Zeit benötigt minimum.
Asymptotische Analyse
Die Komplexität oder Effizienz eines Algorithmus ist die Anzahl der Schritte, die vom Algorithmus ausgeführt werden, um die gewünschte Ausgabe zu erhalten. Eine asymptotische Analyse wird durchgeführt, um die Komplexität eines Algorithmus in seiner theoretischen Analyse zu berechnen. Bei der asymptotischen Analyse wird eine große Eingabelänge verwendet, um die Komplexitätsfunktion des Algorithmus zu berechnen.
Note - - Asymptoticist eine Bedingung, bei der eine Linie dazu neigt, eine Kurve zu treffen, sich jedoch nicht schneidet. Hier sind die Linie und die Kurve zueinander asymptotisch.
Die asymptotische Notation ist der einfachste Weg, um die schnellste und langsamste Ausführungszeit für einen Algorithmus zu beschreiben, der hohe und niedrige Geschwindigkeitsgrenzen verwendet. Hierfür verwenden wir folgende Notationen:
- Big O-Notation
- Omega-Notation
- Theta-Notation
Big O-Notation
In der Mathematik wird die Big O-Notation verwendet, um die asymptotischen Eigenschaften von Funktionen darzustellen. Es repräsentiert das Verhalten einer Funktion für große Eingaben in einer einfachen und genauen Methode. Es ist eine Methode zur Darstellung der Obergrenze der Ausführungszeit eines Algorithmus. Dies stellt die längste Zeit dar, die der Algorithmus benötigen könnte, um seine Ausführung abzuschließen. Die Funktion -
f (n) = O (g (n))
wenn es positive Konstanten gibt c und n0 so dass f(n) ≤ c * g(n) für alle n wo n ≥ n0.
Omega-Notation
Die Omega-Notation ist eine Methode zur Darstellung der Untergrenze der Ausführungszeit eines Algorithmus. Die Funktion -
f (n) = Ω (g (n))
wenn es positive Konstanten gibt c und n0 so dass f(n) ≥ c * g(n) für alle n wo n ≥ n0.
Theta-Notation
Die Theta-Notation ist eine Methode zur Darstellung sowohl der Untergrenze als auch der Obergrenze der Ausführungszeit eines Algorithmus. Die Funktion -
f (n) = θ (g (n))
wenn es positive Konstanten gibt c1, c2, und n0 so dass c1 * g (n) ≤ f (n) ≤ c2 * g (n) für alle ist n wo n ≥ n0.
Beschleunigung eines Algorithmus
Die Leistung eines parallelen Algorithmus wird durch Berechnung seines Algorithmus bestimmt speedup. Die Beschleunigung ist definiert als das Verhältnis der Worst-Case-Ausführungszeit des schnellsten bekannten sequentiellen Algorithmus für ein bestimmtes Problem zur Worst-Case-Ausführungszeit des parallelen Algorithmus.
Anzahl der verwendeten Prozessoren
Die Anzahl der verwendeten Prozessoren ist ein wichtiger Faktor bei der Analyse der Effizienz eines parallelen Algorithmus. Die Kosten für den Kauf, die Wartung und den Betrieb der Computer werden berechnet. Je mehr Prozessoren von einem Algorithmus zur Lösung eines Problems verwendet werden, desto teurer wird das erhaltene Ergebnis.
Gesamtkosten
Die Gesamtkosten eines parallelen Algorithmus ergeben sich aus der zeitlichen Komplexität und der Anzahl der in diesem bestimmten Algorithmus verwendeten Prozessoren.
Gesamtkosten = Zeitkomplexität × Anzahl der verwendeten Prozessoren
deshalb, die efficiency eines parallelen Algorithmus ist -