5. Big O(n log n)

O(n log n) ist eine Zeitkomplexität, die oft bei effizienten Sortieralgorithmen wie Mergesort,
Quicksort (im Durchschnitt) und Heapsort auftritt. Sie bedeutet, dass die Anzahl der Operationen proportional zur Eingabegröße ( n ) und gleichzeitig logarithmisch mit der Anzahl der erforderlichen Teilungen (oder Zusammenführungen) wächst.

O(n log n) ist in vielen Fällen die effizienteste Komplexität für Algorithmen, die durch Vergleich sortieren, da 4. Big O(n) für Vergleichs-basierte Sortieralgorithmen nicht unterschritten werden kann.

Python-Beispiel für O(n log n) (Mergesort):

Hier ein Beispiel für Mergesort, einen Algorithmus, der eine Liste rekursiv in kleinere Teillisten unterteilt und diese dann sortiert zusammenführt. Mergesort hat eine Laufzeit von O(n log n), da es in jeder Teilungsschicht ( n ) Elemente zu sortieren gibt und die Tiefe der rekursiven Aufteilung log(n) beträgt.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr  # Basisfall: ein einzelnes Element ist bereits sortiert

    mid = len(arr) // 2
    left_half = merge_sort(arr[:mid])  # Linke Hälfte sortieren
    right_half = merge_sort(arr[mid:])  # Rechte Hälfte sortieren
    return merge(left_half, right_half)  # Zusammenführen

def merge(left, right):
    sorted_array = []
    while left and right:
        if left[0] < right[0]:
            sorted_array.append(left.pop(0))
        else:
            sorted_array.append(right.pop(0))
    sorted_array.extend(left or right)
    return sorted_array

# Verwendung
my_list = [3, 1, 4, 1, 5, 9]
sorted_list = merge_sort(my_list)
print(sorted_list)  # Ausgabe: [1, 1, 3, 4, 5, 9]

Java-Beispiel für O(n log n) (Mergesort):

In diesem Beispiel wird Mergesort verwendet, um ein Array zu sortieren. Die rekursive Teilung und das anschließende Zusammenführen sorgen dafür, dass der Algorithmus O(n log n) hat.

import java.util.Arrays;

public class Main {
    public static void mergeSort(int[] arr) {
        if (arr.length <= 1) return;

        int mid = arr.length / 2;
        int[] left = Arrays.copyOfRange(arr, 0, mid);
        int[] right = Arrays.copyOfRange(arr, mid, arr.length);

        mergeSort(left);
        mergeSort(right);

        merge(arr, left, right);
    }

    private static void merge(int[] arr, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                arr[k++] = left[i++];
            } else {
                arr[k++] = right[j++];
            }
        }
        while (i < left.length) arr[k++] = left[i++];
        while (j < right.length) arr[k++] = right[j++];
    }

    public static void main(String[] args) {
        int[] myArray = {3, 1, 4, 1, 5, 9};
        mergeSort(myArray);
        System.out.println(Arrays.toString(myArray));  // Ausgabe: [1, 1, 3, 4, 5, 9]
    }
}

In beiden Beispielen hat der Mergesort-Algorithmus eine Zeitkomplexität von O(n log n), weil der Sortierprozess jede Teilung log(n) tief geht und jede dieser Teilungen n Vergleiche benötigt, um die Elemente zusammenzuführen.