KOmplexität

blurry333

Hallo,

ich versteh nicht wie man von einem rekursiven Algorithmus die Komplexität bestimmen soll. Wieviel Speicher braucht er und wie lange braucht er.

Hab gesehen da macht man oft nur grobe Abschätzungen.

Man macht häufig nur Abschätzungen, allerdings braucht man einen Beweis,
wenn man es sauber beantworten will.

Im Grunde überlegt man, wie häufig die Funktion aufgerufen wird,
wenn man ein Datenstruktur der Größe n hat.
Falls Schleifen in der Funktion sind, die abhängig von n sind, ist das ganze
natürlich nicht mehr so einfach. Aber wenn diese z.B. im Durchschnitt n/2
mal ausgeführt werden, dann kann man z.B. einfach wieder mit n multiplizieren.
Richtig kompliziert wird es wenn die Tiefe bei der Anzahl der Wiederholungen
berücksichtigt wird

volkard

blurry333 schrieb:

ich versteh nicht wie man von einem rekursiven Algorithmus die Komplexität bestimmen soll. Wieviel Speicher braucht er und wie lange braucht er.

Hier würde ein Beispiel helfen.

blurry333 schrieb:

Hab gesehen da macht man oft nur grobe Abschätzungen.

Das ist mir neu.

Ad aCTa

> ich versteh nicht wie man von einem rekursiven Algorithmus die Komplexität bestimmen soll. Wieviel Speicher braucht er und wie lange braucht er.

Konkret willst du also die Zeitkomplexität und die Speicherkomplexität erhalten, denn die beiden musst du AFAIK in einem Algorithmus unterscheiden. Allerdings trifft die Komplexität keinerlei Aussage darüber, wie lange ein Algorithmus braucht oder an Speicherplatz benötigt, sondern, wie er sich bei ändernder Größenordnung verhält.
Angenommen:

void recursive(unsigned n) {
   calculation(n);
   --n;
   if(n > 0)
      recursive(n);
}

So, wenn calculation so definiert wurde:

void calculation(unsigned n) { }

ist die Zeitkomplexität direkt proportional zum parameter n, also einfach linear. Sowohl best-case alsauch worst-case sind dann einfach mit ƒ(n) = n zu beschreiben. Theoretisch ändert sich das auch nicht, wenn die Funktion nun anders aussähe:

void calculation(unsigned n) {
   for(unsigned i = 0; i < 100; ++i) {
      i * i;
   }
}

Wird in calculation nun jedoch eine Abhängigkeit mit dem Parameter n gefunden, dann ändert sich das allerdings:
Edit: Nur noch Unfug (siehe unten)

Ad aCTa schrieb:

Jetzt wird schnell klar, dass da eine Beziehung für ƒ(n) = n² + n herrscht. (n² Schleifendurchläufe mit konstanter Berrechnung, n rekursive Aufrufe)

Wirklich? Auch wenn du letztlich bei dem Ergebnis O(n^2) landest, müsstest du den Weg dorthin nochmal gründlich überdenken.

@Ad aCTa:
Für f(n) = c gilt f(n) = O(1), nicht f(n) = O(n).

Deine Begründung für O(recursive) = O(n²) Iterationen kann ich nicht nachvollziehen. Einerseits leuchtet mir das "+ n" nicht ein. Abgesehen davon berechnest du die Anzahl an Iterationen falsch.
Für n = 4 beispielsweise komme ich auf 10 Iterationen (4 + 3 + 2 + 1).
Allgemein: A(n) = 1/2n² + 1/2n
Offensichtlich gilt A(n) = O(1/2n²). Dass O(n²) stimmt, liegt nur daran, dass diese Notation, wie du schon gesagt hast, nur die asymptotisch obere Schranke angibt.

Ad aCTa

Hoppla, das ist mir jetzt ein wenig peinlich. Richtigerweise geht es natürlich so:

void recursive(unsigned n) {
   calculation(n);
   if(n > 0)
      recursive(n - 1); // <--- Was hab ich mir hier vorher nur gedacht?
}

So, für diese Funktion

void calculation(unsigned n)
   for(unsigned i = 0; i < n; ++i) {
      i * n;
   }
}

Wäre natürlich das zu beobachten:
recursive(1) = 1 Call und 1 Schleifendurchlauf
recursive(2) = 2 Calls und 3 Schleifendurchläufe
recursive(3) = 3 Calls und 6 Schleifendurchläufe
recursive(4) = 4 Calls und 10 Schleifendurchläufe

Was auf ƒ(n) = n(n + 1) / 2 folgern sollte. (die Summe der Werte von 1 bis n)
Folglich ƒ(n) = 1/2 * (n² + n). Nach O-Notation sollte das nun O(n² + n), dominierende Funktion daher O(n²). Oder?

Edit: Da ist mir schon jemand zuvor gekommen...