Schlagwort-Archive: Komplexität

Algorithmen und Datenstrukturen: Der Counting Sort in Java

Der Algorithmus

Der Counting Sort ist ein Out-of-place-Sortieralgorithmus, da er das zu sortierende Array im Gegensatz zu Quick Sort oder Bubble Sort nicht direkt sortiert, sondern vorher eine Speicherkopie anlegt, die im Abschluss auf das zu sortierende Array kopiert wird.

Der Algorithmus ist genau dann effizient, wenn man viele (doppelte) Zahlen in einem kleinem Wertebereich / einer engen Min-/Max-Range sortieren möchte.

Wenn man z.B. ein Array mit dem Aufkommen von Menschen nach Alter in der deutschen Bevölkerung sortieren möchte, so hätte man eine Array-Größe von ca. 80 Millionen Einträgen. Da es aber keine Menschen über 120 Jahren in Deutschland gibt, oder der älteste noch lebende Mensch in Deutschland aktuell jünger als 120 Jahre ist, kann man den Wertebereich zwischen 0 und 120 Jahren einschränken.

  • Kleiner Wertebereich: Alter zwischen 0 und 120 Jahren.
  • Großes Array: 80 Millionen Einträge für jeden Menschen

Für diese Fälle eignet sich der Counting Sort Algorithmus ausgezeichnet, da er nach der folgenden Vorgehensweise vor geht:

  • Ermittle den maximalen Wert des Wertebereichs für das Histogramm (z.B. höchstes Alter 120 Jahre)
  • Initialisiere ein sortiertes Histogramm als Array mit 0-Werten.
  • Laufe das große Array in einer O(n)-Schleife durch (z.B. das Array mit den 80 Mio. Menschen)
    • Zähle die Histogramm-Array-Werte über die Vorkommnisse/Häufigkeiten beim Durchlaufen um 1 nach oben, je nachdem welche Zahl bei dem Durchlauf gefunden wird
    • Laufe das erstellte Histogramm-Array von links nach rechts durch und füge die Vorkommnisse der Zahlen in das Ziel-Array ein, so dass bei 2x der Zahl 1 und 4x der Zahl 2 so etwas rauskommt: 1;1;2;2;2;2
  • Auf diese Weise wurde anhand des sortierten Histogramm-Arrays die Zahlenmenge sortiert
package AlgoDat;

import java.util.Arrays;

public class CountingSort {
    // Zu sortierendes Array
    private int myArray[] = {22, 6, 2, 4, 10, 3, 9, 7, 5, 8, 1};

    // Hält die Klasse als instanziertes Objekt
    @SuppressWarnings("unused")
    private static CountingSort program;
    private java.util.Random rnd = new java.util.Random();

    // Hilfsfunktion für das Ausgeben des Arrays
    public void OutputOfIntArray(int myArray[])
    {
        if (myArray != null)
        {
            for (int i = 0; i < myArray.length; i++) {
                if (i > 0) System.out.print(";");
                System.out.print(myArray[i]);
            }

            System.out.println();
        }
    }

    // Generiert ein zufälliges Integer-Array der Größe size mit Werten zwischen 0 und upperLimit
    public int[] generateIntegerArrayOfSize(int size, int upperLimit)
    {       
        int[] generatedArray = new int[size];
        
        for (int i = 0; i < generatedArray.length; i++)
        {
            generatedArray[i] = rnd.nextInt(upperLimit);
        }

        return generatedArray;
    }

    // Konstruktor
    public CountingSort()
    {
        System.out.println("Kleines Array");
        System.out.println("=============");
        System.out.print("Vorher: ");
        this.OutputOfIntArray(myArray);

        long startTime = System.nanoTime();
        this.sort(myArray, false);
        long endTime = System.nanoTime();

        System.out.print("Nachher: ");
        this.OutputOfIntArray(myArray);

        System.out.println("Ich habe " + (endTime-startTime) + " ns mit einem Array von " + myArray.length + " und einem Wertebereich/Histogramm von " + Arrays.stream(myArray).max().getAsInt() + " Zahlen gebraucht! \n\n");

        System.out.println("Großes Array, kleiner Wertebereich");
        System.out.println("==================================");
        System.out.print("Vorher: ");
        int[] grossesArray = this.generateIntegerArrayOfSize(10000000, 100000);

        startTime = System.nanoTime();
        this.sort(grossesArray, false);
        endTime = System.nanoTime();

        System.out.println("Ich habe " + (endTime-startTime) + " ns mit einem Array von " + grossesArray.length + " und einem Wertebereich/Histogramm von " + Arrays.stream(grossesArray).max().getAsInt() + " Zahlen gebraucht! \n\n");

        System.out.println("Kleines Array, großer Wertebereich");
        System.out.println("==================================");
        System.out.print("Vorher: ");
        int[] kleinesArray = this.generateIntegerArrayOfSize(100000, 10000000);

        startTime = System.nanoTime();
        this.sort(kleinesArray, false);
        endTime = System.nanoTime();

        System.out.println("Ich habe " + (endTime-startTime) + " ns mit einem Array von " + kleinesArray.length + " und einem Wertebereich/Histogramm von " + Arrays.stream(kleinesArray).max().getAsInt() + " Zahlen gebraucht! \n\n");
    }

    public void sort(int[] myArray) 
    {
        this.sort(myArray, true);
    }

    public void sort(int[] myArray, boolean verbose) 
    {
        //int maxValue = findMax(elements);
        int maxValue = Arrays.stream(myArray).max().getAsInt();
        int[] counts = new int[maxValue + 1];

        // Phase 1: Erstelle das Histogramm
        for (int element : myArray) 
        {
            counts[element]++;
        }

        if (verbose)
        {
            System.out.println("Erstelle Histogramm als Array mit den Häufigkeiten der Zahlen im Array");
        
            // Optional - kann auskommentiert werden: Headline von Histogramm und Ausgabe Histogramm
            for (int i = 0; i < maxValue; i++)
            {
                System.out.print(i);

                if (i + 1 != maxValue)
                {
                    System.out.print(";");
                }
            }

            System.out.println("");
            this.OutputOfIntArray(counts);
        }

        // Phase 2: Aggregiere die Zahlen, um die Startadressen in Zielarray zu ermitteln
        for (int i = 1; i <= maxValue; i++) 
        {
            // Die Daten im Array werden von links nach rechts kummuliert
            // um die Startadresse für jede Zahl zu bekommen.
            counts[i] += counts[i - 1];
        }

        if (verbose)
        {
            System.out.println("Array mit den aggregierten Zahlen (Histogramm) für die Startadresse im Zielarray:");
            this.OutputOfIntArray(counts);
        }

        // Phase 3: Schreibe die Zahlen ins Zielarray
        int[] target = new int[myArray.length];

        for (int i = myArray.length - 1; i >= 0; i--) 
        {
            int element = myArray[i];
            
            counts[element] = counts[element] - 1;

            if (verbose)
            {
                System.out.println("Schreibe " + element +" an Index " + counts[element] + " des zu sortierten Arrays!");
            }

            target[counts[element]] = element;
        }

        // Copy target back to input array
        System.arraycopy(target, 0, myArray, 0, myArray.length);
    } 

    public static void main(String[] args) 
    {
        // Instanziere aus den statischem Programm ein echtes Objekt
        // damit nicht alle Methoden und Variablen static sein müssen.
        program = new CountingSort();
    }
}

Ausgabe

Kleines Array
=============
Vorher: 22;6;2;4;10;3;9;7;5;8;1
Nachher: 1;2;3;4;5;6;7;8;9;10;22
Ich habe 12449300 ns mit einem Array von 11 und einem Wertebereich/Histogramm von 22 Zahlen gebraucht! 


Großes Array, kleiner Wertebereich (Ausgabe aus)
================================================
Ich habe 75933500 ns mit einem Array von 10000000 und einem Wertebereich/Histogramm von 99999 Zahlen gebraucht! 


Kleines Array, großer Wertebereich (Ausgabe aus)
================================================
Ich habe 25634500 ns mit einem Array von 100000 und einem Wertebereich/Histogramm von 9999905 Zahlen gebraucht! 

Komplexität: O-Notation (Ordnung)

Die Laufzeit der Funktion hängt von {\displaystyle n} (Anzahl der Elemente des Eingabearrays) und {\displaystyle k} (die Größe des Zahlenintervalls) ab. Die for-Schleifen werden jeweils {\displaystyle n}-mal oder {\displaystyle k}-mal durchlaufen. Die Zeitkomplexität von Countingsort beträgt somit {\displaystyle {\mathcal {O}}(n+k)}.

Algorithmen und Datenstrukutren: Binäre Suche vs. lineare Suche in JAVA

Der Algorithmus

Die binäre Suche funktioniert nur auf einem bereits sortiertem Datenbestand, daher wird die Zeit für das Sortieren des Arrays „myArray“ mit Merge-Sort auf die Such-Zeit addiert. Da die 11 Elemente im Beispiel-Array sehr wenige sind, sind die Zeiten in ms wenig repräsentativ.

package AlgoDat;
 
public class SearchAlgorithm {
    // Zu durchsuchendes Array
    private int myArray[] = {22, 6, 2, 4, 10, 3, 9, 7, 5, 8, 1};
     
    // Hält die Klasse als instanziertes Objekt
    @SuppressWarnings("unused")
    private static SearchAlgorithm program;
 
    public int linearSearch(int[] array, int contentToSearchFor)
    {
        for (int i = 0; i < array.length; i++)
        {
            if (array[i] == contentToSearchFor)
            {
                return i;
            }
        }
 
        return -1;
    }
 
    public int binarySearch(int[] myArray, int contentToSearchFor)
    {
        // Start conditions
        int lowIndex = 0;
        int highIndex = myArray.length - 1;
 
        while (lowIndex <= highIndex)
        {
            int middlePosition = (lowIndex + highIndex) / 2;
            int middleContent = myArray[middlePosition];
 
            if (contentToSearchFor == middleContent) 
            {
                return middlePosition;
            }
 
            // Halbieren der Suchelemente
            if (contentToSearchFor < middleContent)
            {
                highIndex = middlePosition - 1;
            }
            else
            {
                lowIndex = middlePosition + 1;
            }
        }
 
        // Außerhalb der While-Schleife wissen wir, dass wir
        // das Element nicht gefunden haben :-(
        return -1;
    }
 
    // Konstruktor
    public SearchAlgorithm()
    {
        int arrayContent = -1;
        long startTime = 0;
        long endTime = 0;
        int index = -1;
        long passedTime = 0;
 
        System.out.println("Lineare Suche");
        System.out.println("=============");
        // Not found
        arrayContent = 23;
        startTime = System.nanoTime();
        index = linearSearch(myArray, arrayContent);
        System.out.print("Der Array-Element mit dem Inhalt '" + arrayContent + "' wurde nicht gefunden in myArray[]. ");
        endTime =  System.nanoTime();
        passedTime = endTime - startTime;
        System.out.println("Lineare Suche not found: " + passedTime + " ms.");
         
        // Best case
        arrayContent = 22;
        startTime =  System.nanoTime();
        index = linearSearch(myArray, arrayContent);
        System.out.print("Der Array-Element mit dem Inhalt '" + arrayContent + "' befindet sich am Index " + index + " von myArray[]. ");
        endTime =  System.nanoTime();
        passedTime = endTime - startTime;
        System.out.println("Lineare Suche Best-Case: " + passedTime + " ms.");
 
        // Average case
        arrayContent = 3;
        startTime =  System.nanoTime();
        index = linearSearch(myArray, arrayContent);
        System.out.print("Der Array-Element mit dem Inhalt '" + arrayContent + "' befindet sich am Index " + index + " von myArray[]. ");
        endTime =  System.nanoTime();
        passedTime = endTime - startTime;
        System.out.println("Lineare Suche Average-Case: " + passedTime + " ms.");
 
        // Worst case
        arrayContent = 1;
        startTime =  System.nanoTime();
        index = linearSearch(myArray, arrayContent);
        System.out.print("Der Array-Element mit dem Inhalt '" + arrayContent + "' befindet sich am Index " + index + " von myArray[]. ");
        endTime =  System.nanoTime();
        passedTime = endTime - startTime;
        System.out.println("Lineare Suche Worst-Case: " + passedTime + " ms.");
 
        System.out.println("Binäre Suche");
        System.out.println("============");
 
        /*********************************************/
        /* die binäre Suche benötigt ein sortiertes  */
        /* Array, damit sie funktioniert.            */
        /*********************************************/
        startTime = System.nanoTime();
        this.mergeSort(myArray);
        endTime =  System.nanoTime();
        long passedSortTime = endTime - startTime;
 
        // Not found
        arrayContent = 23;
        startTime = System.nanoTime();
        index = binarySearch(myArray, arrayContent);
        System.out.print("Der Array-Element mit dem Inhalt '" + arrayContent + "' wurde nicht gefunden in myArray[]. ");
        endTime =  System.nanoTime();
        passedTime = passedSortTime + (endTime - startTime);
        System.out.println("Binäre Suche not found: " + passedTime + " ms.");
         
        // Best case
        arrayContent = 22;
        startTime =  System.nanoTime();
        index = binarySearch(myArray, arrayContent);
        System.out.print("Der Array-Element mit dem Inhalt '" + arrayContent + "' befindet sich am Index " + index + " von myArray[]. ");
        endTime =  System.nanoTime();
        passedTime = passedSortTime + (endTime - startTime);
        System.out.println("Binäre Suche erstes Element: " + passedTime + " ms.");
 
        // Average case
        arrayContent = 3;
        startTime =  System.nanoTime();
        index = binarySearch(myArray, arrayContent);
        System.out.print("Der Array-Element mit dem Inhalt '" + arrayContent + "' befindet sich am Index " + index + " von myArray[]. ");
        endTime =  System.nanoTime();
        passedTime = passedSortTime + (endTime - startTime);
        System.out.println("Binäre Suche mittleres Element: " + passedTime + " ms.");
 
        // Worst case
        arrayContent = 1;
        startTime =  System.nanoTime();
        index = binarySearch(myArray, arrayContent);
        System.out.print("Der Array-Element mit dem Inhalt '" + arrayContent + "' befindet sich am Index " + index + " von myArray[]. ");
        endTime =  System.nanoTime();
        passedTime = passedSortTime + (endTime - startTime);
        System.out.println("Binäre Suche letztes Element: " + passedTime + " ms.");
    }
 
    public static void main(String[] args) 
    {
        // Instanziere aus den statischem Programm ein echtes Objekt
        // damit nicht alle Methoden und Variablen static sein müssen.
        program = new SearchAlgorithm();
    }
 
    /**************/
    /* MERGE SORT */
    /**************/
 
    public void mergeSort(int myArray[])
    {
        // Abbruchbedingung der Rekursion im Sinne von Teile-und-Herrsche-Algorithmen
        if (myArray.length == 1) return;
 
        // weist bei ungeraden Zahlen eine abgerundete Ganzzahl zu
        int indexHaelfte = myArray.length / 2;
 
        int[] linkeHaelfte = new int[indexHaelfte];
 
        // Die abgerundete Ganzzahl kann von der Länge abgezogen werden
        // um die Größe des rechten Arrays zu erhalten.
        int[] rechteHaelfte = new int[myArray.length - indexHaelfte];
 
        // Befülle die linke Hälfte 
        for (int i = 0; i < indexHaelfte; i++)
        {
            linkeHaelfte[i] = myArray[i];
        }
 
        // Befülle die rechte Hälfte 
        for (int i = indexHaelfte; i < myArray.length; i++)
        {
            rechteHaelfte[i - indexHaelfte] = myArray[i];
        }
 
        // Hier ist der rekursive Aufruf, indem die beiden Hälften an
        // die mergeSort-Methode selbst übergeben wird.
        this.mergeSort(linkeHaelfte);
        this.mergeSort(rechteHaelfte);
 
        // Hier werden die beiden Arrays wieder kombiniert (geMerged)
        this.merge(myArray, linkeHaelfte, rechteHaelfte);
    }
 
    private void merge(int[] mergeArray, int[] linkeHaelfte, int[] rechteHaelfte)
    {
        int iteratorLinks = 0, iteratorRechts = 0, iteratorMergeArray = 0;
 
        // Da die linke und reche Hälfte bereits sortiert sind, funktioniert die Zuweisung
        // in ein neues Array mit einer einzigen Schleife der Komplexität/Ordnung O(n).
        while (iteratorLinks < linkeHaelfte.length && iteratorRechts < rechteHaelfte.length)
        {
            if (linkeHaelfte[iteratorLinks] <= rechteHaelfte[iteratorRechts])
            {
                mergeArray[iteratorMergeArray] = linkeHaelfte[iteratorLinks];
                iteratorLinks++;
            }
            else
            {
                mergeArray[iteratorMergeArray] = rechteHaelfte[iteratorRechts];
                iteratorRechts++;
            }
 
            iteratorMergeArray++;
        }
 
        // Wenn noch Elemente in der linken Hälfte waren, die nicht verglichen wurden,
        // werden diese dem Merged Array hinzugefügt
        while (iteratorLinks < linkeHaelfte.length)
        {
            mergeArray[iteratorMergeArray] = linkeHaelfte[iteratorLinks];
            iteratorLinks++;
            iteratorMergeArray++;
        }
 
        // Wenn noch Elemente in der rechten Array-Hälfte waren, die nicht verglichen wurden,
        // werden diese dem Merged Array hinzugefügt
        while (iteratorRechts < rechteHaelfte.length)
        {
            mergeArray[iteratorMergeArray] = rechteHaelfte[iteratorRechts];
            iteratorRechts++;
            iteratorMergeArray++;
        }
    }
}

Ausgabe

Lineare Suche
=============
Der Array-Element mit dem Inhalt '23' wurde nicht gefunden in myArray[]. Lineare Suche not found: 20969800 ms.
Der Array-Element mit dem Inhalt '22' befindet sich am Index 0 von myArray[]. Lineare Suche Best-Case: 9613200 ms.
Der Array-Element mit dem Inhalt '3' befindet sich am Index 5 von myArray[]. Lineare Suche Average-Case: 337400 ms.
Der Array-Element mit dem Inhalt '1' befindet sich am Index 10 von myArray[]. Lineare Suche Worst-Case: 270200 ms.
 
Binäre Suche
============
Der Array-Element mit dem Inhalt '23' wurde nicht gefunden in myArray[]. Binäre Suche not found: 206800 ms.
Der Array-Element mit dem Inhalt '22' befindet sich am Index 10 von myArray[]. Binäre Suche erstes Element: 271400 ms.
Der Array-Element mit dem Inhalt '3' befindet sich am Index 2 von myArray[]. Binäre Suche mittleres Element: 306700 ms.
Der Array-Element mit dem Inhalt '1' befindet sich am Index 0 von myArray[]. Binäre Suche letztes Element: 302800 ms.

Komplexität: O-Notation (Ordnung)

Die Komplexität der binären Suche wird mit

beschrieben, wobei die Komplexität des vorangegangenen Merge-Sort-Algorithmus mitgerechnet werden muss, da die binäre Suche nur auf einem binären Datenbestand funktioniert. Somit ergibt sich

, wobei die additiven Bestandteile log(n) wegfallen. Somit ergibt sich im vorliegenden Falle die Komplexität O(n*log(n)) wegen der vorangegangen Sortierung. Ist diese nicht notwendig bleibt es bei der O-Notation O(log(n)).

Algorithmen und Datenstrukturen: O-Notation / Komplexität der rekursiven Fakultät

Der Algorithmus

Bei der rekursiven Fakultät handelt es sich um einen rekursiven Funktionsaufruf:

package AlgoDat;
 
public class RekursiveFakultaet {
    // Zu sortierendes Array
     
    // Hält die Klasse als instanziertes Objekt
    @SuppressWarnings("unused")
    private static RekursiveFakultaet program;
 
    public long berechneFakultaet(int teilFakultaet)
    {
        // Abbruchbedingung der Rekursion wenn 1 erreicht ist
        if (teilFakultaet == 1) return 1;
 
        // Multipliziere rekursiv f(n) = n * f(n - 1) bis 1
        return teilFakultaet * berechneFakultaet(teilFakultaet - 1);
    }
 
    // Konstruktor
    public RekursiveFakultaet()
    {
        System.out.println(this.berechneFakultaet(25) + "");        
    }
 
    public static void main(String[] args) 
    {
        // Instanziere aus den statischem Programm ein echtes Objekt
        // damit nicht alle Methoden und Variablen static sein müssen.
        program = new RekursiveFakultaet();
    }
}

Ausgabe

7034535277573963776

Komplexität: O-Notation (Ordnung)

Der rekursive Aufruf dieser Art kann als primitiv rekursiven Klasse gezählt werden und besitzt die lineare Komplexität / O-Notation: