6. Big O(n²)

O(n²) beschreibt eine quadratische Zeitkomplexität und tritt häufig bei Algorithmen auf, die verschachtelte Schleifen enthalten, wie etwa bei vielen Sortieralgorithmen wie Bubblesort oder Insertion Sort (wenn sie nicht optimiert sind).

Quadratische Algorithmen sind oft ineffizient bei großen Eingabemengen, da die Laufzeit schnell zunimmt: Verdoppelt sich die Eingabegröße, vervierfacht sich die Laufzeit.

Python-Beispiel für O(n²) (Bubblesort):

Hier ist ein Beispiel für Bubblesort, einen einfachen Sortieralgorithmus mit einer quadratischen Zeitkomplexität. Er vergleicht jedes Paar benachbarter Elemente und tauscht sie, wenn sie in der falschen Reihenfolge sind. Bei jeder Durchlaufrunde durch das Array muss Bubblesort erneut n-1 Vergleiche anstellen, was insgesamt zu einer O(n²)-Komplexität führt.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):  # Gehe durch die Liste bis zum unsortierten Teil
            if arr[j] > arr[j + 1]:  # Tausche, wenn die aktuelle Zahl größer ist
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

# Verwendung
my_list = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(my_list)
print(my_list)  # Ausgabe: [11, 12, 22, 25, 34, 64, 90]

Java-Beispiel für O(n²) (Bubblesort):

Hier ein ähnliches Beispiel in Java. Die Methode [[bubbleSort]] sortiert das Array durch wiederholtes Tauschen benachbarter Elemente, wenn sie in der falschen Reihenfolge sind.

import java.util.Arrays;

public class Main {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {  // Tausche, wenn das aktuelle Element größer ist
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] myArray = {64, 34, 25, 12, 22, 11, 90};
        bubbleSort(myArray);
        System.out.println(Arrays.toString(myArray));  // Ausgabe: [11, 12, 22, 25, 34, 64, 90]
    }
}

In beiden Beispielen durchläuft Bubblesort das Array mehrfach, wobei jede Runde ( n - i - 1 ) Vergleiche macht. Die Anzahl der Vergleiche summiert sich quadratisch zur Eingabegröße, was zu einer O(n²)-Laufzeit führt.