Python - Algorithmusanalyse

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.

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.