Grobanalyse von Algorithmen

Eine erste grobe Einschätzung über die Effizienz eines Algorithmus ist schnell mit einer Grobanalyse erstellt. Der Algorithmus wird als Blackbox betrachtet und Speicher und CPU Auslastungen wird außer Acht gelassen. Was zählt ist nur die Zeit die für die Durchführung benötigt wird.

Die hierfür verwendeten drei gängigen Methoden sind: Arithmetisch, Geometrisch und Harmonisch.
Die Laufzeit (Berechnung eines Elementes von n) berechnet sich bei allen mit: Durchführungsdauer / Anzahl der Elemente.

Arithmetisches Mittel

Die Problematik am Arithmetischen Mittel sind die, meist zu beginn, stark abweichenden (negativ ausschlagende) Ergebnise. Die Anzahl der zu bearbeitenden Elementen hat oft Auswirkungen auf die Durchführungszeit. Deshalb wird das Gesamtergebnis mit dem Arithmetischen Mittel oft zu beginn verfälscht.

Geometrisches Mittel

Das Geometrische Mittel kann nur mit positiven Zahlen gebildet werden. (Obwohl eine negative Durchführungsdauer sehr wünschenswert wäre  😉 ) Der Vorteil gegenüber des Arithmetischen Mittels ist, dass Extremwerte kaum einen Einfluss auf das Gesamtergebnis nimmt.

Harmonisches Mittel

Das für die Grobanalyse bevorzugte Mittel ist das Harmonische Mittel. Für die Berechnung von Geschwindigkeiten (in unsrem Fall die Durchführungszeit) eignet sich am besten das Harmonische Mittel. Leicht zu berechnen und keine Ausschläge bei Extermwerten.

Beispiel

In folgendem Beispiel werden von 100 bis 900 (in Einhundert Schritten) Daten (Zufallszahlen) mit dem Shakesort und dem Bubblesort sortiert. [ms]

ShakesortBubblesort

 

 

Schreibe einen Kommentar

Diese Website verwendet Akismet, um Spam zu reduzieren. Erfahre mehr darüber, wie deine Kommentardaten verarbeitet werden.