7. Big O(n³)

O(n³) beschreibt eine kubische Zeitkomplexität und tritt häufig bei Algorithmen auf, die drei verschachtelte Schleifen verwenden.

Diese Art von Algorithmus wird oft in komplexen Berechnungen verwendet, wie z.B. bei der Verarbeitung von 3D-Daten oder in bestimmten dynamischen Programmierungsansätzen. Die Laufzeit eines kubischen Algorithmus wächst schnell mit der Größe der Eingabe, da sich die Laufzeit mit dem Würfel der Eingabemenge erhöht.

Python-Beispiel für O(n³) (Matrixmultiplikation):

Hier ist ein Beispiel für die Multiplikation zweier ( n \times n )-Matrizen, was eine kubische Zeitkomplexität aufweist. Bei der Matrixmultiplikation werden drei verschachtelte Schleifen verwendet, um die einzelnen Elemente zu berechnen.

def matrix_multiply(A, B):
    n = len(A)
    # Ergebnis-Matrix initialisieren
    C = [[0 for _ in range(n)] for _ in range(n)]
    
    for i in range(n):  # Iteration über die Zeilen von A
        for j in range(n):  # Iteration über die Spalten von B
            for k in range(n):  # Iteration über die Elemente
                C[i][j] += A[i][k] * B[k][j]  # Multiplikation und Addition
    return C

# Verwendung
A = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

B = [
    [9, 8, 7],
    [6, 5, 4],
    [3, 2, 1]
]

result = matrix_multiply(A, B)
for row in result:
    print(row)  # Ausgabe: Zeilen der Ergebnis-Matrix

Java-Beispiel für O(n³) (Matrixmultiplikation):

Hier ein ähnliches Beispiel in Java. Die Methode matrixMultiply multipliziert zwei Matrizen und verwendet ebenfalls drei verschachtelte Schleifen.

public class Main {
    public static int[][] matrixMultiply(int[][] A, int[][] B) {
        int n = A.length;
        int[][] C = new int[n][n];  // Ergebnis-Matrix initialisieren
        
        for (int i = 0; i < n; i++) {  // Iteration über die Zeilen von A
            for (int j = 0; j < n; j++) {  // Iteration über die Spalten von B
                for (int k = 0; k < n; k++) {  // Iteration über die Elemente
                    C[i][j] += A[i][k] * B[k][j];  // Multiplikation und Addition
                }
            }
        }
        return C;
    }

    public static void main(String[] args) {
        int[][] A = {
            {1, 2, 3},
            {4, 5, 6},
            {7, 8, 9}
        };

        int[][] B = {
            {9, 8, 7},
            {6, 5, 4},
            {3, 2, 1}
        };

        int[][] result = matrixMultiply(A, B);
        for (int[] row : result) {
            for (int val : row) {
                System.out.print(val + " ");  // Ausgabe der Zeilen der Ergebnis-Matrix
            }
            System.out.println();
        }
    }
}

In beiden Beispielen ist die Zeitkomplexität O(n³), da jede der drei Schleifen n Iterationen durchläuft. Das führt dazu, dass die Laufzeit exponentiell ansteigt, wenn die Größe der Matrizen erhöht wird.