Programmieren mit Harald R. Haberstroh

Dies ist eine Mini-Einführung in die O-Notation. Wer es genau wissen will, soll gleich unten bei der Literaturliste bzw. den Links weitermachen.

Die O-Notation (engl. Big O Notation) wird in der Informatik zu Beschreibung der Komplexität (und damit der Laufzeit) eines Algorithmus. Die O-Notation beschreibt den schlechtesten Fall (worst-case scenario). Sie beschreibt die Ausführungszeit oder den Speicheraufwand, den ein Algorithmus benötigt.

Alle, die Programming Pearls (Programming Pearls (ACM Press)) oder irgend ein anderes Informatik Buch lesen und kein fundiertes mathematisches Wissen haben, werden sich den Kopf stoßen, sobald sie Kapitel erreichen, in denen so komische Dinge wie O(N log N) vorkommen. Ich hoffe, dieser Beitrag wird zu einem besseren Verständnis der Grundlagen zur O-Notation verhelfen.

Für Programmierer sind wahrscheinlich kurze Code-Beispiele am Besten geeignet die O-Notation zu verstehen. Die Beispiele zeigen die übliche Reihenfolge der Komplexität, von einfachen bis zu aufwendigen Beispielen.

O(1)

O(1) beschreibt einen Algorithmus, der immer die selbe Zeit (oder den selben Speicher) benötigt, unabhängig von der Größe der Eingabedaten.

boolean isFirstElementNull(String[] strings) {
    if (strings[0] == null) {
        return true;
    }
    return false;
}

Es ist (hoffentlich) offensichtlich, dass diese Funktion immer gleich lange braucht, egal wie groß das String-Array ist (Außer natürlich, wenn strings == null oder strings.length == 0 ist, denn da kommt es zu einer Exception! Diese Sonderfälle lassen wir weg.).

O(N)

O(N) beschreibt Algorithmen, deren Laufzeit linear in direkter Proportionalität zur Größe des Eingabedatensatzes wachsen (z.B. dreimal so große Eingabe bewirkt eine dreimal so lange Laufzeit). Das folgende Beispiel zeigt auch, dass die O-Notation den schlechtesten (worst-case) Fall beschreibt. Die gesuchte Zahl kann natürlich in jedem Schleifendurchlauf gefunden werden und die Funktion frühzeitig beenden, aber die O-Notation beschreibt die obere Grenze, bei der die maximale Anzahl Schleifendurchläufe benötigt wird.

boolean containsValue(int[] values, int value) {
    for (int i = 0; i < values.length; i++) {
        if (value == values[i]) { // always the same time!
            return true;
        }
    }
    return false;
}

O(N²)

O(N²) repräsentiert Algorithmen, deren Laufzeit direkt proportional zum Quadrat der Größe des Eingabedatensatzes sind. Das ist üblicherweise bei verschachtelten Schleifen der Fall. Tiefer verschachtelte Schleifen resultieren demnach in O(N³), O(N⁴) etc.

boolean containsDuplicates(int[] values) {
    for (int i = 0; i < values.length; i++) {
        for (int j = 0; j < values.length; j++) {
            if (i == j) { // don't compare self
                continue;
            }
            if (values[i] == values[j]) {
                return true;
            }
        }
    }
    return false;
}

O(2^N)

O(2^N) beschreibt Algorithmen, deren Laufzeit sich für jedes weitere Element der Eingabedaten verdoppelt. Die Ausführungszeit einer O(2^N) Funktion wird sehr schnell sehr groß. Das folgende Beispiel zeigt einen Algorithmus, der alle möglichen Zeichenfolgen eines Strings liefert (permutiert). Permutationen sind üblicherweise exponentiell (allgemein O(k^N) für ein bestimmtes k).

public static void permutation(String str) { 
    permutation("", str); 
}

private static void permutation(String prefix, String str) {
    int n = str.length();
    if (n == 0) {
        System.out.println(prefix);
    } else {
        for (int i = 0; i < n; i++) {
            permutation(prefix + str.charAt(i), 
                str.substring(0, i) + str.substring(i+1, n));
        }
    }
}

Primzahlenbestimmung hat auch exponentiellen Aufwand (O(k^N)).

Logarithmus O(log N)

Ich werde logarithmisches Verhalten an einem üblichen Beispiel erklären:

Denken Sie an ein Telefonbuch, welches Einträge sortiert nach Name, Vorname und Adresse (in dieser Reihenfolge) enthält. Wie würde man die Suche nach der Telefonnummer eines bestimmten Teilnehmers mit gegebenem Namen programmieren? Nehmen wir an, das Telefonbuch hätte 1.000.000 Einträge.

Wenn man linear sucht, dann ist der Aufwand O(N), also maximal 1.000.000 Schleifendurchläufe (im Durchschnitt 500.000). Geschickter ist jedoch die Binäre Suche, bei der man zunächst den 500.000 Eintrag nimmt und prüft. Ist das der gesuchte Name, dann ist man fertig. Ist der gesuchte Name größer (also alphabetisch weiter hinten), dann teilt man die obere Hälfte wieder in zwei Teile und vergleicht mit dem mittleren Eintrag (750.000). Ist der Eintrag nun größer als der gesuchte, dann teilt man die untere Hälfte und nimmt die Mitte ((750.000 - 500.000) / 2 + 500.000 = 625.000) usw. Nach spätestens 20 Teilungen hat man den Namen gefunden (oder er ist nicht im Telefonbuch).

Bei 3 Einträgen benötigt man höchstens 2 Schritte, bei 7 höchstens 3, bei 15 höchstens 4, bei 1000 höchstens 10 und bei 1.000.000 höchstens 20 Schritte.

Der Aufwand ist also O(log N), wobei es egal ist, welche Basis man für den Logarithmus nimmt, weil sich die Logarithmen nur durch Konstante unterscheiden, welche man bei der O-Notation weglassen kann. Die O-Notation gilt nämlich nur für große Werte von N, so dass sich Konstante praktisch nicht mehr auswirken. Die binäre Suche hat eigentlich den Aufwand von log₂ N, welcher sich nur durch den konstanten Wert log 2 (Logarithmus von 2) unterscheidet.

// nums ... sorted array
public static int binarySearch(int[] nums, int check) {
    int hi = nums.length - 1;
    int lo = 0;
    while (hi >= lo) {
        guess = lo + ((hi - lo) / 2);
        if (nums[guess] > check) {
            hi = guess - 1;
        } else if (nums[guess] < check) {
            lo = guess + 1;
        } else {
            return guess;
        }
    }
    return -1;
}

Obiges Beispiel zeigt die binäre Suche mit einem sortierten int-Arrays nums und der zu suchenden Zahl check. Zurückgeliefert wird der Index oder -1, wenn die Zahl nicht in dem Array vorkommt.

Der log N ist die Umkehrung von 10^N und log₂ N die Umkehrung von 2^N.

Es gilt:

O(1) < O(log N) < O(N) < O(N log N) < O(N²) < O(N³) < O(k^N)

Quellen

Jon Bentley: Programming Pearls
Binäre Suche (Wikipedia)
Donald E. Knuth: The Art of Computer Programming
BIG-O Notation
Plain English explanation of Big O
Big O, how do you calculate/approximate it?
A Beginner’s Guide to Big O Notation

Labels: algorithmen, Informatik, POS1-2, POS1-3

# Eingestellt von Harald R. Haberstroh @ 19:44