8. Big O(2ⁿ)

O(2ⁿ) beschreibt eine exponentielle Zeitkomplexität und tritt häufig bei Algorithmen auf, die eine Fibonacci-Zahlenfolge oder ähnliche rekursive Probleme berechnen, bei denen jeder Schritt zwei neue Teilprobleme erzeugt.

Exponentielle Algorithmen sind in der Regel sehr ineffizient, da die Laufzeit dramatisch ansteigt, wenn die Eingabegröße nur geringfügig erhöht wird.

Python-Beispiel für O(2ⁿ) (Fibonacci-Zahlen):

Hier ist ein Beispiel zur Berechnung der n-ten Fibonacci-Zahl mit einer einfachen rekursiven Methode, die eine exponentielle Zeitkomplexität aufweist. Diese Methode ruft sich für jedes ( n ) zweimal auf, was zu einer Laufzeit von O(2ⁿ) führt.

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

# Verwendung
n = 5
print(f"Die {n}-te Fibonacci-Zahl ist: {fibonacci(n)}")  # Ausgabe: 5

Java-Beispiel für O(2ⁿ) (Fibonacci-Zahlen):

Hier ein ähnliches Beispiel in Java. Die Methode fibonacci berechnet ebenfalls die n-te Fibonacci-Zahl rekursiv.

public class Main {
    public static int fibonacci(int n) {
        if (n <= 1) return n;
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

    public static void main(String[] args) {
        int n = 5;
        System.out.println("Die " + n + "-te Fibonacci-Zahl ist: " + fibonacci(n));  // Ausgabe: 5
    }
}

In beiden Beispielen wird die Fibonacci-Zahl mit einer rekursiven Funktion berechnet, die für jedes n zwei neue Funktionsaufrufe erzeugt. Diese Struktur führt zu einer exponentiellen Wachstumsrate der Laufzeit, was die Zeitkomplexität O(2ⁿ) ergibt.

Hinweis:

Exponentielle Algorithmen sind oft nur für kleine Werte von ( n ) praktikabel. Für effizientere Berechnungen von Fibonacci-Zahlen sollten iterative oder memoization-basierte Ansätze in Betracht gezogen werden, die die Laufzeit auf 4. Big O(n) reduzieren können.