algorithm
Big-O-Notation

Bemerkungen

Eine einfache Schleife

Die folgende Funktion findet das maximale Element in einem Array:

int find_max(const int *array, size_t len) {
    int max = INT_MIN;
    for (size_t i = 0; i < len; i++) {
        if (max < array[i]) {
            max = array[i];
        }
    }
    return max;
}

Die Eingabegröße ist die Größe des Arrays, das ich im Code als len .

Zählen wir die Operationen.

int max = INT_MIN;
size_t i = 0;

Diese beiden Zuweisungen werden nur einmal ausgeführt, das sind also zwei Operationen. Die Operationen, die geloopt werden, sind:

if (max < array[i])
i++;
max = array[i]

Da es drei Operationen in der Schleife gibt und die Schleife n-mal ausgeführt wird, addieren wir 3n zu unseren bereits vorhandenen 2 Operationen, um 3n + 2 . Daher benötigt unsere Funktion 3n + 2 Operationen, um das Maximum zu finden (die Komplexität beträgt 3n + 2 ). Dies ist ein Polynom, bei dem der am schnellsten wachsende Term ein Faktor von n ist, also O (n).

Sie haben wahrscheinlich bemerkt, dass "Operation" nicht sehr gut definiert ist. Ich habe zum Beispiel gesagt, dass, if (max < array[i]) eine Operation wäre, diese Anweisung jedoch je nach Architektur drei Anweisungen kompilieren kann: einen Speicherlesevorgang, einen Vergleich und einen Zweig. Ich habe auch alle Vorgänge als gleich betrachtet, obwohl beispielsweise die Speichervorgänge langsamer als die anderen sind und ihre Leistung stark schwankt, beispielsweise aufgrund von Cache-Effekten. Ich habe die return-Anweisung, die Tatsache, dass ein Frame für die Funktion erstellt wird, vollständig ignoriert. Letztendlich spielt es bei der Komplexitätsanalyse keine Rolle, denn egal, wie ich Operationen zähle, ändert sich nur der Koeffizient des n-Faktors und der Konstante, so ist das Ergebnis immer noch O (n). Die Komplexität zeigt, wie der Algorithmus mit der Größe der Eingabe skaliert. Dies ist jedoch nicht der einzige Aspekt der Leistung!

Eine verschachtelte Schleife

Die folgende Funktion prüft, ob ein Array Duplikate enthält, indem jedes Element genommen wird und dann das gesamte Array durchlaufen wird, um zu sehen, ob das Element vorhanden ist

_Bool contains_duplicates(const int *array, size_t len) {
    for (int i = 0; i < len - 1; i++) {
        for (int j = 0; j < len; j++) {
            if (i != j && array[i] == array[j]) {
                return 1;
            }
        }
    }
    return 0;
}

Die innere Schleife führt bei jeder Iteration eine Anzahl von Operationen aus, die konstant mit n . Die äußere Schleife führt auch einige konstante Operationen aus und führt die innere Schleife n mal aus. Die äußere Schleife selbst wird n mal ausgeführt. Die Operationen innerhalb der inneren Schleife werden also n^2 mal ausgeführt, die Operationen in der äußeren Schleife werden n mal ausgeführt und die Zuweisung an i wird einmal ausgeführt. Somit ist die Komplexität so etwas wie an^2 + bn + c , und da der höchste Term n^2 , ist die O-Notation O(n^2) .

Wie Sie vielleicht bemerkt haben, können wir den Algorithmus verbessern, indem Sie die gleichen Vergleiche nicht mehrmals durchführen. Wir können in der inneren Schleife von i + 1 aus beginnen, da alle Elemente vor diesem Element bereits gegen alle Array-Elemente geprüft wurden, einschließlich der Elemente am Index i + 1 . Dies ermöglicht es uns, den i == j Check fallen zu lassen.

_Bool faster_contains_duplicates(const int *array, size_t len) {
    for (int i = 0; i < len - 1; i++) {
        for (int j = i + 1; j < len; j++) {
            if (array[i] == array[j]) {
                return 1;
            }
        }
    }
    return 0;
}

Offensichtlich führt diese zweite Version weniger Operationen aus und ist daher effizienter. Wie lässt sich das auf Big-O-Notation übersetzen? Nun, der innere Schleifenkörper wird nun 1 + 2 + ... + n - 1 = n(n-1)/2 mal ausgeführt. Dies ist immer noch ein Polynom zweiten Grades, und so ist es immer noch nur O(n^2) . Wir haben die Komplexität deutlich reduziert, da wir die Anzahl der Operationen, die wir ausführen, grob um 2 dividiert haben, aber wir befinden uns immer noch in derselben Komplexitätsklasse , wie sie von Big-O definiert wird. Um die Komplexität auf eine niedrigere Klasse zu senken, müssten wir die Anzahl der Operationen durch etwas teilen, das mit n gegen unendlich geht .

Ein O (log n) Beispiel

Einführung

Betrachten Sie das folgende Problem:

L ist eine sortierte Liste mit n vorzeichenbehafteten Ganzzahlen ( n ist groß genug), zum Beispiel [-5, -2, -1, 0, 1, 2, 4] (hier hat n einen Wert von 7). Wenn bekannt ist, dass L die ganze Zahl 0 enthält, wie können Sie den Index von 0 finden?

Naiver Ansatz

Das erste, was mir einfällt, ist, einfach jeden Index zu lesen, bis 0 gefunden wird. Im schlimmsten Fall ist die Anzahl der Operationen n , die Komplexität ist also O (n).

Dies funktioniert gut für kleine Werte von n , aber gibt es einen effizienteren Weg?

Dichotomie

Betrachten Sie den folgenden Algorithmus (Python3):

a = 0
b = n-1
while True:
  h = (a+b)//2 ## // is the integer division, so h is an integer
  if L[h] == 0:
    return h
  elif L[h] > 0:
    b = h
  elif L[h] < 0:
    a = h

a und b sind die Indizes, zwischen denen 0 zu finden ist. Jedes Mal, wenn wir die Schleife betreten, verwenden wir einen Index zwischen a und b und verwenden ihn, um den zu durchsuchenden Bereich einzuengen.

Im schlimmsten Fall müssen wir warten, bis a und b gleich sind. Aber wie viele Operationen dauert das? Nicht n, denn jedes Mal, wenn wir die Schleife betreten, dividieren wir den Abstand zwischen a und b durch etwa zwei. Die Komplexität ist vielmehr O (log n).

Erläuterung

Hinweis: Wenn wir "log" schreiben, meinen wir den binären Logarithmus oder die Protokollbasis 2 (die wir "log_2" schreiben werden). Da O (log_2 n) = O (log n) (Sie können die Mathematik ausführen), verwenden wir "log" anstelle von "log_2".

Nennen wir x die Anzahl der Operationen: Wir wissen, dass 1 = n / (2 ^ x) ist.

Also 2 ^ x = n, dann x = log n

Fazit

Bedenken Sie bei aufeinanderfolgenden Trennungen (sei es durch zwei oder durch eine beliebige Anzahl), dass die Komplexität logarithmisch ist.

O (log n) Typen von Algorithmen

Nehmen wir an, wir haben ein Problem der Größe n. Nun wird für jeden Schritt unseres Algorithmus (den wir schreiben müssen) unser ursprüngliches Problem die Hälfte seiner vorherigen Größe (n / 2).

Bei jedem Schritt wird unser Problem zur Hälfte.

Wenn der Problemraum verkleinert (dh vollständig gelöst) ist, kann er nach dem Verlassen der Prüfbedingung nicht weiter reduziert werden (n wird gleich 1).

1. Sagen wir zum kten Schritt oder zur Anzahl der Operationen:

   Problemgröße = 1

2. Aber wir wissen im kten Schritt, unsere Problemgröße sollte sein:

   Problemgröße = n / 2 ^k

3. Von 1 und 2:

   n / 2 ^k = 1 oder

   n = 2 ^k

4. Log auf beiden Seiten

   log _e n = k log _e 2

   oder

   k = log _e n / log _e 2

5. Verwenden Sie das Formelprotokoll _x m / log _x n = log _n m

   k = log ₂ n

   oder einfach k = log n

Jetzt wissen wir, dass unser Algorithmus maximal bis zu Log n laufen kann, daher kommt Zeitkomplexität als
O (log n)

Ein sehr einfaches Beispiel für den Code, der den obigen Text unterstützt, ist:

for(int i=1; i<=n; i=i*2)
{
    // perform some operation
}

Wenn Sie nun gefragt wird, ob n gleich 256 ist, wie viele Schritte diese Schleife (oder ein anderer Algorithmus, der die Problemgröße halbiert) ausgeführt wird, können Sie dies sehr einfach berechnen.

k = log ₂ 256

k = log ₂ 2 ⁸ (=> log _a a = 1)

k = 8

Ein weiteres sehr gutes Beispiel für einen ähnlichen Fall ist der binäre Suchalgorithmus .

int bSearch(int arr[],int size,int item){
 int low=0;
 int high=size-1;

 while(low<=high){                 
     mid=low+(high-low)/2;                 
     if(arr[mid]==item)                        
         return mid;                 
     else if(arr[mid]<item)                         
         low=mid+1;                
     else  high=mid-1;      
     }  
  return –1;// Unsuccessful result
}