2. Big O(log n)

Logarithmische Zeitkomplexität bei Algorithmen, die Eingabegröße in jedem Schritt halbieren.

Besonders effizient für große Datenmengen - minimale Operationen nötig.

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

In diesem Beispiel wird die binary_search-Funktion verwendet, um in einer sortierten Liste nach einem Zielwert zu suchen. Die Anzahl der Vergleiche wächst logarithmisch mit der Liste, weil der Algorithmus in jedem Schritt die Hälfte der verbleibenden Elemente ausschließt.

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid  # Ziel gefunden
        elif arr[mid] < target:
            left = mid + 1  # Rechte Hälfte durchsuchen
        else:
            right = mid - 1  # Linke Hälfte durchsuchen
    return -1  # Ziel nicht gefunden

# Verwendung
my_list = [1, 3, 5, 7, 9]
print(binary_search(my_list, 7))  # Ausgabe: 3

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

In diesem Java-Beispiel wird ebenfalls die binäre Suche verwendet, um in einem Array nach einem Zielwert zu suchen. Der Algorithmus halbiert bei jedem Schritt den Suchbereich und hat daher eine Laufzeit von O(log n).

public class Main {
    public static int binarySearch(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == target) {
                return mid;  // Ziel gefunden
            } else if (arr[mid] < target) {
                left = mid + 1;  // Rechte Hälfte durchsuchen
            } else {
                right = mid - 1;  // Linke Hälfte durchsuchen
            }
        }
        return -1;  // Ziel nicht gefunden
    }

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

Da der Suchbereich bei jedem Schritt halbiert wird, ist der Aufwand logarithmisch, d.h., selbst für eine große Eingabe wächst die Laufzeit nur langsam.