2. Big O(log n)

O(log n) beschreibt eine logarithmische Zeitkomplexität und tritt häufig bei Algorithmen auf, die die Eingabegröße in jedem Schritt halbieren oder durch eine konstante Zahl reduzieren.

Diese Art von Algorithmus ist besonders effizient, da sie mit einer minimalen Anzahl von Operationen große Datenmengen durchsuchen kann.

Ein häufiges Beispiel für O(log n) ist die binäre Suche, bei der die Anzahl der zu prüfenden Elemente bei jedem Schritt halbiert wird.

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.