Bestimmung der Komplexität gegebener Codes

Lesezeit: 15 Minuten

Benutzer-Avatar
Jiew Meng

Wie können Sie bei einem gegebenen Codeschnipsel die Komplexität im Allgemeinen bestimmen? Ich finde mich sehr verwirrt mit Big-O-Fragen. Zum Beispiel eine ganz einfache Frage:

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        System.out.println("*");
    }
}

Der TA erklärte das mit so etwas wie Kombinationen. So ist n, wähle 2 = (n(n-1))/2 = n^2 + 0,5 und entferne dann die Konstante, sodass es n^2 wird. Ich kann Testwerte eingeben und ausprobieren, aber wie kommt diese Kombinationssache herein?

Was ist, wenn es eine if-Anweisung gibt? Wie wird die Komplexität bestimmt?

for (int i = 0; i < n; i++) {
    if (i % 2 ==0) {
        for (int j = i; j < n; j++) { ... }
    } else {
        for (int j = 0; j < i; j++) { ... }
    }
}

Was ist dann mit Rekursion …

int fib(int a, int b, int n) {
    if (n == 3) {
        return a + b;
    } else {
        return fib(b, a+b, n-1);
    }
}

Benutzer-Avatar
Umarmung

Im Algemeinengibt es keine Möglichkeit, die Komplexität einer gegebenen Funktion zu bestimmen

Warnung! Textwand eintreffend!

1. Es gibt sehr einfach Algorithmen, von denen niemand weiß, ob sie überhaupt anhalten oder nicht.

Es gibt kein Algorithmus die entscheiden können, ob ein bestimmtes Programm anhält oder nicht, wenn eine bestimmte Eingabe erfolgt. Die Berechnung der Rechenkomplexität ist ein noch schwierigeres Problem, da wir nicht nur beweisen müssen, dass der Algorithmus anhält, sondern auch beweisen müssen wie schnell es tut es.

//The Collatz conjecture states that the sequence generated by the following
// algorithm always reaches 1, for any initial positive integer. It has been
// an open problem for 70+ years now.
function col(n){
    if (n == 1){
        return 0;
    }else if (n % 2 == 0){ //even
        return 1 + col(n/2);
    }else{ //odd
        return 1 + col(3*n + 1);
    }
}

2. Einige Algorithmen haben seltsame und ausgefallene Komplexitäten

Ein allgemeines “Komplexitätsbestimmungsschema” würde wegen dieser Typen leicht zu kompliziert werden

//The Ackermann function. One of the first examples of a non-primitive-recursive algorithm.
function ack(m, n){
    if(m == 0){
        return n + 1;
    }else if( n == 0 ){
        return ack(m-1, 1);
    }else{
        return ack(m-1, ack(m, n-1));
    }
}

function f(n){ return ack(n, n); }

//f(1) = 3
//f(2) = 7
//f(3) = 61
//f(4) takes longer then your wildest dreams to terminate.

3. Einige Funktionen sind sehr einfach, werden aber viele Arten von statischen Analyseversuchen verwirren

//Mc'Carthy's 91 function. Try guessing what it does without
// running it or reading the Wikipedia page ;)
function f91(n){
    if(n > 100){
        return n - 10;
    }else{
        return f91(f91(n + 11));
    }
}

Das heißt, wir brauchen immer noch einen Weg, um die Komplexität von Dingen zu finden, oder? For-Schleifen sind ein einfaches und weit verbreitetes Muster. Nehmen Sie Ihr erstes Beispiel:

for(i=0; i<N; i++){
   for(j=0; j<i; j++){
       print something
   }
}

Seit jeder print something O(1) ist, wird die zeitliche Komplexität des Algorithmus dadurch bestimmt, wie oft wir diese Zeile ausführen. Nun, wie Ihr TA erwähnt hat, tun wir dies, indem wir uns in diesem Fall die Kombinationen ansehen. Die innere Schleife läuft (N + (N-1) + … + 1) mal, also insgesamt (N+1)*N/2.

Da wir Konstanten vernachlässigen, erhalten wir O(N2).

Jetzt können wir für die kniffligeren Fälle mathematischer vorgehen. Versuchen Sie, eine Funktion zu erstellen, deren Wert darstellt, wie lange die Ausführung des Algorithmus angesichts der Größe N der Eingabe dauert. Oft können wir eine rekursive Version dieser Funktion direkt aus dem Algorithmus selbst konstruieren, und so wird die Berechnung der Komplexität zum Problem, dieser Funktion Grenzen zu setzen. Wir nennen diese Funktion a Wiederauftreten

Zum Beispiel:

function fib_like(n){
    if(n <= 1){
        return 17;
    }else{
        return 42 + fib_like(n-1) + fib_like(n-2);
    }
 }

Es ist leicht zu sehen, dass die Laufzeit in Bezug auf N durch gegeben ist

T(N) = 1 if (N <= 1)
T(N) = T(N-1) + T(N-2) otherwise

Nun, T(N) ist nur die gute alte Fibonacci-Funktion. Wir können die Induktion verwenden, um dem einige Grenzen zu setzen.

Zum Beispiel, Beweisen wir durch Induktion, dass T(N) <= 2^n für alle N (dh T(N) ist O(2^n))

  • Basisfall: n = 0 oder n = 1
    T(0) = 1 <= 1 = 2^0
    T(1) = 1 <= 2 = 2^1
  • induktiver Fall (n > 1):
    T(N) = T(n-1) + T(n-2)
    aplying the inductive hypothesis in T(n-1) and T(n-2)...
    T(N) <= 2^(n-1) + 2^(n-2)
    so..
    T(N) <= 2^(n-1) + 2^(n-1)
         <= 2^n

(Wir können versuchen, etwas Ähnliches zu tun, um auch die Untergrenze zu beweisen)

In den meisten Fällen können Sie mit einer guten Schätzung der endgültigen Laufzeit der Funktion Wiederholungsprobleme einfach mit einem Induktionsbeweis lösen. Dazu musst du natürlich erst raten können – hier hilft dir nur viel Übung.

Und als letzte Anmerkung möchte ich auf die hinweisen Hauptsatzdie einzige Regel für schwierigere Wiederholungsprobleme, die mir jetzt einfällt und die häufig verwendet wird. Verwenden Sie es, wenn Sie mit einem kniffligen Teile-und-Herrsche-Algorithmus umgehen müssen.


In Ihrem “falls Fall” -Beispiel würde ich das auch lösen, indem ich schummele und es in zwei separate Schleifen aufteile, die anziehen. Ich habe kein if drin.

for (int i = 0; i < n; i++) {
    if (i % 2 ==0) {
        for (int j = i; j < n; j++) { ... }
    } else {
        for (int j = 0; j < i; j++) { ... }
    }
}

Hat die gleiche Laufzeit wie

for (int i = 0; i < n; i += 2) {
    for (int j = i; j < n; j++) { ... }
}

for (int i = 1; i < n; i+=2) {
    for (int j = 0; j < i; j++) { ... }
}

Und jeder der beiden Teile kann leicht als O(N^2) für eine Gesamtsumme gesehen werden, die ebenfalls O(N^2) ist.

Beachten Sie, dass ich hier einen guten Trick benutzt habe, um das “if” loszuwerden. Dafür gibt es keine allgemeine Regel, wie das Beispiel des Collatz-Algorithmus zeigt

  • Gute Antwort. Und ich stimme zu. Aber wie wäre es, offtopic zu sein und zu versuchen, die Komplexität einer Funktion zu finden, indem man sie mit Daten füttert und sie statistisch analysiert? Offensichtlich wird es nicht für alle Arten von Funktionen funktionieren und manchmal ist es sehr unpraktisch – aber es könnte Ihnen ein zufriedenstellendes Ergebnis liefern, wenn Sie nur die Parameterspanne beweisen können, oder?

    – Stefan

    8. November 2011 um 18:04 Uhr

  • @stephan: Programm-Benchmarks sind oft zu ungenau, um “schöne” Komplexitätsgrenzen (im theoretischen Sinne) zu liefern, aber sie sind immer noch von unschätzbarem Wert, um einen Einblick in schwierige Probleme zu geben (z. B. durchschnittliche Fallanalyse oder Probleme, die stark eingabeabhängig sind). )

    – Umarmung

    8. November 2011 um 18:31 Uhr

  • @missingno Hmm, ein traditionelles Benchmark-Programm (Profiler) wird nicht das tun, was ich mir vorgestellt habe. Ich dachte eher daran, ein parametrisiertes Erregungs-Rig mit gut definierten Spannen einzurichten. Diese Daten könnten dann durch einfache Mathematik angenähert werden, um uns die Funktion der Komplexität zu geben. Das Erhalten von Big-O aus dieser Funktion ist trivial.

    – Stefan

    9. November 2011 um 0:11 Uhr

  • Das Problem ist, dass für die kleinen Ns, die Sie bewerten können, zu viele Dinge passieren, die die Asymptotik durcheinander bringen, was bedeutet, dass Sie nur eine sehr grobe Schätzung erhalten, die wahrscheinlich nicht viel besser ist als das, was Sie bereits vorher wussten – versuchen Sie, O (n) von zu unterscheiden O(n log n) 😉 in einem Diagramm. Außerdem ist es für die wirklich schwierigen Probleme sehr schwierig, umfassende Benchmarks zu erstellen, da so viele Dinge die Laufzeit beeinflussen können (Sie wissen, wann die Dinge außer Kontrolle geraten sind, wenn die Leute anfangen zu verwenden Physik Terminologie auf ihren Papieren :P)

    – Umarmung

    9. November 2011 um 0:26 Uhr

  • Der Schüler von Collatz versucht, seine Vermutung zu beweisen: i-programmer.info/news/112-theorie/… – 32 Seiten lang, jedoch hat er auf Seite 11 einen Fehler gemacht.

    – Alwin K.

    9. November 2011 um 6:16 Uhr


Im Allgemeinen ist es theoretisch unmöglich, die Komplexität des Algorithmus zu bestimmen.

Eine coole und codezentrierte Methode, dies zu tun, besteht jedoch darin, tatsächlich nur direkt in Begriffen von Programmen zu denken. Nehmen Sie Ihr Beispiel:

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        System.out.println("*");
    }
}

Jetzt wollen wir seine Komplexität analysieren, also fügen wir einen einfachen Zähler hinzu, der die Anzahl der Ausführungen der inneren Zeile zählt:

int counter = 0;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        System.out.println("*");
        counter++;
    }
}

Da die Zeile System.out.println keine Rolle spielt, entfernen wir sie:

int counter = 0;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        counter++;
    }
}

Jetzt, da wir nur noch den Zähler übrig haben, können wir die innere Schleife natürlich vereinfachen:

int counter = 0;
for (int i = 0; i < n; i++) {
    counter += n;
}

… weil wir wissen, dass das Inkrement exakt gefahren wird n mal. Und jetzt sehen wir, dass der Zähler um erhöht wird n exakt n Mal, also vereinfachen wir dies zu:

int counter = 0;
counter += n * n;

Und wir kamen mit dem (richtigen) O(n) heraus2) Komplexität 🙂 Es ist da im Code 🙂

Schauen wir uns an, wie dies für einen rekursiven Fibonacci-Rechner funktioniert:

int fib(int n) {
  if (n < 2) return 1;
  return fib(n - 1) + fib(n - 2);
}

Ändern Sie die Routine so, dass sie die Anzahl der darin verbrachten Iterationen anstelle der tatsächlichen Fibonacci-Zahlen zurückgibt:

int fib_count(int n) {
  if (n < 2) return 1;
  return fib_count(n - 1) + fib_count(n - 2);
}

Es ist immer noch Fibonacci! 🙂 Wir wissen jetzt also, dass der rekursive Fibonacci-Rechner die Komplexität O(F(n)) hat, wobei F die Fibonacci-Zahl selbst ist.

Ok, schauen wir uns etwas Interessanteres an, sagen wir einfaches (und ineffizientes) Mergesort:

void mergesort(Array a, int from, int to) {
  if (from >= to - 1) return;
  int m = (from + to) / 2;
  /* Recursively sort halves */
  mergesort(a, from, m);
  mergesort(m, m,    to);
  /* Then merge */
  Array b = new Array(to - from);
  int i = from;
  int j = m;
  int ptr = 0;
  while (i < m || j < to) {
    if (i == m || a[j] < a[i]) {
      b[ptr] = a[j++];
    } else {
      b[ptr] = a[i++];
    }
    ptr++;
  }
  for (i = from; i < to; i++)
    a[i] = b[i - from];
}

Da uns nicht das eigentliche Ergebnis, sondern die Komplexität interessiert, ändern wir die Routine so, dass sie tatsächlich die Anzahl der durchgeführten Arbeitseinheiten zurückgibt:

int mergesort(Array a, int from, int to) {
  if (from >= to - 1) return 1;
  int m = (from + to) / 2;
  /* Recursively sort halves */
  int count = 0;
  count += mergesort(a, from, m);
  count += mergesort(m, m,    to);
  /* Then merge */
  Array b = new Array(to - from);
  int i = from;
  int j = m;
  int ptr = 0;
  while (i < m || j < to) {
    if (i == m || a[j] < a[i]) {
      b[ptr] = a[j++];
    } else {
      b[ptr] = a[i++];
    }
    ptr++;
    count++;
  }
  for (i = from; i < to; i++) {
    count++;
    a[i] = b[i - from];
  }
  return count;
}

Dann entfernen wir die Zeilen, die sich nicht auf die Anzahl auswirken, und vereinfachen:

int mergesort(Array a, int from, int to) {
  if (from >= to - 1) return 1;
  int m = (from + to) / 2;
  /* Recursively sort halves */
  int count = 0;
  count += mergesort(a, from, m);
  count += mergesort(m, m,    to);
  /* Then merge */
  count += to - from;
  /* Copy the array */
  count += to - from;
  return count;
}

Noch etwas vereinfachen:

int mergesort(Array a, int from, int to) {
  if (from >= to - 1) return 1;
  int m = (from + to) / 2;
  int count = 0;
  count += mergesort(a, from, m);
  count += mergesort(m, m,    to);
  count += (to - from) * 2;
  return count;
}

Auf das Array können wir jetzt eigentlich verzichten:

int mergesort(int from, int to) {
  if (from >= to - 1) return 1;
  int m = (from + to) / 2;
  int count = 0;
  count += mergesort(from, m);
  count += mergesort(m,    to);
  count += (to - from) * 2;
  return count;
}

Wir können jetzt sehen, dass eigentlich die absoluten Werte von von und bis nicht mehr wichtig sind, sondern nur noch ihre Entfernung, also modifizieren wir dies zu:

int mergesort(int d) {
  if (d <= 1) return 1;
  int count = 0;
  count += mergesort(d / 2);
  count += mergesort(d / 2);
  count += d * 2;
  return count;
}

Und dann kommen wir zu:

int mergesort(int d) {
  if (d <= 1) return 1;
  return 2 * mergesort(d / 2) + d * 2;
}

Hier offensichtlich d Beim ersten Aufruf ist die Größe des zu sortierenden Arrays, sodass Sie die Wiederholung für die Komplexität M (x) haben (dies ist in der zweiten Zeile gut sichtbar 🙂

M(x) = 2(M(x/2) + x)

und das müssen Sie lösen, um zu einer geschlossenen Formlösung zu gelangen. Dies tun Sie am einfachsten, indem Sie die Lösung M(x) = x log x erraten und für die rechte Seite überprüfen:

2 (x/2 log x/2 + x)
        = x log x/2 + 2x
        = x (log x - log 2 + 2)
        = x (log x - C)

und überprüfen Sie, ob es asymptotisch äquivalent zur linken Seite ist:

x log x - Cx
------------ = 1 - [Cx / (x log x)] = 1 - [C / log x] --> 1 - 0 = 1.
x log x

Obwohl dies eine zu starke Verallgemeinerung ist, stelle ich mir Big-O gerne in Form von Listen vor, bei denen die Länge der Liste N Elemente beträgt.

Wenn Sie also eine for-Schleife haben, die über alles in der Liste iteriert, ist es O (N). In Ihrem Code haben Sie eine Zeile, die (allein isoliert) 0 (N) ist.

for (int i = 0; i < n; i++) {

Wenn Sie eine for-Schleife in einer anderen for-Schleife verschachtelt haben und für jedes Element in der Liste eine Operation ausführen, die erfordert, dass Sie sich jedes Element in der Liste ansehen, dann führen Sie eine Operation N-mal für jedes von N Elementen aus O(N^2). In Ihrem obigen Beispiel haben Sie tatsächlich eine weitere for-Schleife in Ihrer for-Schleife verschachtelt. Sie können sich das also so vorstellen, als ob jede for-Schleife 0 (N) ist, und sie dann, weil sie verschachtelt sind, miteinander multiplizieren, um einen Gesamtwert von 0 (N ^ 2) zu erhalten.

Umgekehrt, wenn Sie nur eine schnelle Operation an einem einzelnen Element durchführen, wäre das O (1). Es gibt keine ‘Liste der Länge n’, die durchgegangen werden muss, sondern nur eine einzige einmalige Operation. Um dies in Zusammenhang zu bringen, in Ihrem obigen Beispiel die Operation:

if (i % 2 ==0)

ist 0(1). Wichtig ist nicht das „wenn“, sondern die Tatsache, dass die Überprüfung, ob ein einzelnes Element gleich einem anderen Element ist, eine schnelle Operation für ein einzelnes Element ist. Wie zuvor ist die if-Anweisung in Ihrer externen for-Schleife verschachtelt. Da es sich jedoch um 0 (1) handelt, multiplizieren Sie alles mit „1“, sodass es in Ihrer endgültigen Berechnung für die Laufzeit der gesamten Funktion keine „merklichen“ Auswirkungen gibt.

Für Protokolle und den Umgang mit komplexeren Situationen (wie dieses Geschäft des Zählens bis j oder i und nicht nur wieder n) würde ich Sie auf eine elegantere Erklärung hinweisen hier.

Benutzer-Avatar
dbeer

Ich verwende gerne zwei Dinge für die Big-O-Notation: Standard-Big-O, was das Worst-Case-Szenario darstellt, und durchschnittliches Big-O, was normalerweise passiert. Es hilft mir auch, mich daran zu erinnern, dass die Big-O-Notation versucht, die Laufzeit als Funktion von N, der Anzahl der Eingaben, zu approximieren.

Der TA erklärte das mit so etwas wie Kombinationen. So ist n, wähle 2 = (n(n-1))/2 = n^2 + 0,5 und entferne dann die Konstante, sodass es n^2 wird. Ich kann Testwerte eingeben und ausprobieren, aber wie kommt diese Kombinationssache herein?

Wie gesagt, normales Big-O ist das Worst-Case-Szenario. Sie können versuchen zu zählen, wie oft jede Zeile ausgeführt wird, aber es ist einfacher, sich nur das erste Beispiel anzusehen und zu sagen, dass es zwei Schleifen über die Länge von n gibt, eine in die andere eingebettet, also ist es n * n. Wenn sie hintereinander wären, wäre es n + n, gleich 2n. Da es sich um eine Annäherung handelt, sagen Sie einfach n oder linear.

Was ist, wenn es eine if-Anweisung gibt? Wie wird die Komplexität bestimmt?

Hier hilft es mir sehr, meine Gedanken zu ordnen, wenn ich den durchschnittlichen Fall und den besten Fall habe. Im schlimmsten Fall ignorieren Sie das if und sagen n^2. Im Durchschnitt haben Sie in Ihrem Beispiel eine Schleife über n, wobei eine weitere Schleife über einen Teil von n die Hälfte der Zeit passiert. Dies gibt Ihnen n * n/x/2 (das x ist der Bruchteil von n, der in Ihren eingebetteten Schleifen durchlaufen wird. Dies gibt Ihnen n ^ 2/(2x), also würden Sie genau das gleiche n ^ 2 erhalten. Dies liegt daran, dass es sich um eine Annäherung handelt.

Ich weiß, dass dies keine vollständige Antwort auf Ihre Frage ist, aber hoffentlich wirft es ein Licht auf die Annäherung von Komplexitäten im Code.

Wie in den obigen Antworten gesagt wurde, ist es eindeutig nicht möglich, dies für alle Codeschnipsel zu bestimmen. Ich wollte der Diskussion nur die Idee hinzufügen, den durchschnittlichen Fall Big-O zu verwenden.

Für den ersten Ausschnitt sind es nur n^2, weil Sie n Operationen n Mal ausführen. Wenn j wurde initialisiert ioder ging zu idie Erklärung, die Sie gepostet haben, wäre angemessener, ist es aber derzeit nicht.

Für das zweite Snippet können Sie leicht erkennen, dass die Hälfte der Zeit das erste ausgeführt wird und die zweite die andere Hälfte der Zeit. Je nachdem, was da drin ist (hoffentlich abhängig von n), können Sie die Gleichung rekursiv umschreiben.

Die rekursiven Gleichungen (einschließlich des dritten Schnipsels) können als solche geschrieben werden: die dritte würde erscheinen als

T(n) = T(n-1) + 1

Was wir leicht sehen können, ist O(n).

Benutzer-Avatar
Minthos

Big-O ist nur eine Annäherung, es sagt nicht aus, wie lange die Ausführung eines Algorithmus dauert, es sagt nur etwas darüber aus, wie viel länger es dauert, wenn die Größe seiner Eingabe wächst.

Wenn also die Eingabe die Größe N hat und der Algorithmus einen Ausdruck konstanter Komplexität auswertet: O(1) N mal, ist die Komplexität des Algorithmus linear: O(N). Wenn der Ausdruck lineare Komplexität hat, hat der Algorithmus quadratische Komplexität: O(N*N).

Einige Ausdrücke haben eine exponentielle Komplexität: O(N^N) oder eine logarithmische Komplexität: O(log N). Multiplizieren Sie für einen Algorithmus mit Schleifen und Rekursion die Komplexität jeder Schleifen- und/oder Rekursionsebene. In Bezug auf die Komplexität sind Schleifen und Rekursion gleichwertig. Ein Algorithmus, der in verschiedenen Phasen des Algorithmus unterschiedliche Komplexitäten aufweist, wählen Sie die höchste Komplexität und ignorieren Sie den Rest. Und schließlich werden alle konstanten Komplexitäten als äquivalent betrachtet: O(5) ist dasselbe wie O(1), O(5*N) ist dasselbe wie O(N).

1386170cookie-checkBestimmung der Komplexität gegebener Codes

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy