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.

    internal abstract class Runtime
    {
        private List<Tuple<double, int>> loggedData = new List<Tuple<double, int>>();

        public List<Tuple<double, int>> Data { get { return loggedData; } }

        internal void Push(double elapsedTime, int elements)
        {
            loggedData.Add(new Tuple<double, int>(elapsedTime, elements));
        }

        protected double CalcRuntimePerElement(double elapsedTime, int elements)
        {
            return elapsedTime / elements;
        }

        internal abstract double CalcTotalRuntime();
    }

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.

    internal class Arithmetical : Runtime
    {
        internal override double CalcTotalRuntime()
        {
            return Data.Sum(d => CalcRuntimePerElement(d.Item1, d.Item2)) / Data.Count;
        }
    }

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.

        internal override double CalcTotalRuntime()
        {
            double multResult = 1.0f;
            Data.ForEach(d => multResult *= CalcRuntimePerElement(d.Item1, d.Item2));
            return Math.Pow(multResult, 1.0d / Data.Count);
        }

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.

&nbsp;    internal class Harmonical : Runtime
    {
        internal override double CalcTotalRuntime()
        {
            return Data.Count / Data.Sum(d => 1 / CalcRuntimePerElement(d.Item1, d.Item2));
        }
    }

Beispiel

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

ShakesortBubblesort

 

 

Hinterlasse einen Kommentar

Please Login to comment
  Subscribe  
Notify of