9. Big O(n!)

O(n!) beschreibt eine fakultative Komplexität und ist eine der höchsten Komplexitätsklassen in der Informatik.
Die Ausführungszeit wächst extrem schnell mit der Anzahl der Eingaben, weil jeder neue Input die Gesamtoperationen um das Produkt aller vorangehenden Zahlen erweitert.

Dieser Komplexitätstyp tritt häufig bei Algorithmen auf, die Permutationen oder Kombinationen aller Elemente prüfen, wie etwa das Durchprobieren aller möglichen Reihenfolgen.

Ein typisches Beispiel ist das Berechnen aller Permutationen einer Liste.

Python-Beispiel für O(n!):

In diesem Beispiel berechnet die Funktion generate_permutations alle möglichen Permutationen einer Liste. Die Anzahl der Permutationen wächst mit n!, was die Funktion zu einem O(n!)-Algorithmus macht.

from itertools import permutations

def generate_permutations(lst):
    perms = list(permutations(lst))  # Erzeugt alle Permutationen
    for perm in perms:
        print(perm)

# Verwendung
my_list = [1, 2, 3]
generate_permutations(my_list)
# Ausgabe:
# (1, 2, 3)
# (1, 3, 2)
# (2, 1, 3)
# (2, 3, 1)
# (3, 1, 2)
# (3, 2, 1)

Java-Beispiel für O(n!):

Hier ein Beispiel für das Generieren aller Permutationen eines Arrays in Java. Beachte, dass der rekursive Ansatz dazu führt, dass alle Permutationen generiert werden, was ebenfalls O(n!) ergibt.

public class Main {
    public static void generatePermutations(Integer[] arr, int index) {
        if (index == arr.length - 1) {
            for (int num : arr) {
                System.out.print(num + " ");
            }
            System.out.println();
            return;
        }

        for (int i = index; i < arr.length; i++) {
            swap(arr, index, i);
            generatePermutations(arr, index + 1);
            swap(arr, index, i);  // Rückgängig machen (Backtracking)
        }
    }

    private static void swap(Integer[] arr, int i, int j) {
        Integer temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        Integer[] myArray = {1, 2, 3};
        generatePermutations(myArray, 0);
        // Ausgabe:
        // 1 2 3
        // 1 3 2
        // 2 1 3
        // 2 3 1
        // 3 1 2
        // 3 2 1
    }
}

In diesen Beispielen wächst die Anzahl der Berechnungen extrem schnell, da für eine Liste von 3 Elementen bereits (3! = 6) Permutationen erzeugt werden, und für eine Liste von 4 Elementen sind es schon (4! = 24).