Analyse rekursiven Codes

pac89

hallo, ich muss die laufzeit von folgendem code (siehe bild) analysieren. ich weiß, aber nicht wie das geht. kann mir da jmd. weiterhelfen?

die musterlösung ist:

T(n) = 3*T(n-1) + c1*n^2+ c2*n + c3

ich kenne also die musterlösung. allerdings weiß ich nicht, wie man darauf kommt...bitte daher um hilfe..

der Code lautet:

int rekursion2(int n){

if(n <= 0)
return n*n;

int wert = rekursion2(n-1) * (rekursion2(n-1) + 2);
 n--;
  int sum = 0;
   for(int i = 0; i < n; i++){
      for(int j = n; j > 0; j--){
           sum += i * j;
  }
}
return wert * rekursion2(n);
}

so dazu habe ich mir folgendes überlegt:

also das 3*T(n-1) kommt daher, dass die funktion 3mal rekursiv aufgerufen wird mit dem parameter n-1. man könnte glauben, dass es 2mal mit n-1 und nur einmal mit n aufgerufen wird, aber so ist es nicht. das n wird ja mit n-- erniedrigt, sodass T(n-1) rauskommt.

so zu dem c2*n^2 habe mir die schleifen angeguckt. da wird ja die äußere schleife von null bis zum ende und die innere schleife vom Ende bis 0, also rückwärts durchlaufen. man kommt also insgesamt auf n^2. die konstante davor und fertig.

nun zu c3*n . ich weiß nicht woher das n kommt. kann mir das jmd. vtl. erklären?

wäre über jede hilfe dankbar. hab auch keine seite gefunden wo einem das richtig gut erklärt wird.

knivil

pac89 schrieb:

n wird ja mit n-- erniedrigt

Erniedrigt ...

ich weiß nicht woher das n kommt. kann mir das jmd. vtl. erklären

Tja, das kann ich dir auch nicht sagen, gibt viele Moeglichkeiten/Gruende. Normalerweise ist der Term voellig uninteressant, da der lineare als auch der konstante Anteil vom quadratischem aufgefressen wird.

pac89

ja, die musterlösung hat mich auch echt verwirrt....normalerweise ist das nicht so schwer...aber naja..

Bashar

Der lineare Term ist der konstante Aufwand innerhalb der äußeren Schleife, also Update und Test der Schleifenvariable i sowieso Initialisierung der inneren Schleifenvariable j.

pac89

mit dem linearen term ist doch jetzt in diesem fall c*n gemeint, oder ?

apropo: gibt es irgendwie regeln dazu, wie man soetwas angeht, oder worauf man bei sowas achten soll, oder kann man das nur durch ausprobieren herauskriegen...

Bashar

pac89 schrieb:

mit dem linearen term ist doch jetzt in diesem fall c*n gemeint, oder ?

Ja. Halt der Term, nach dem du gefragt hast.

apropo: gibt es irgendwie regeln dazu, wie man soetwas angeht, oder worauf man bei sowas achten soll, oder kann man das nur durch ausprobieren herauskriegen...

Sorry, aber ich kenne weder Regeln, und ich hab auch nichts ausprobiert. Da bleibt nur nachdenken. Hat bisher aber immer ausgereicht

pac89

okay. ne mein problem war einfach dass ich auf das cn nicht gekommen wäre. der rest davor war eigtl. gar kein problem und die konstante davor hättte ich auch noch hingeschrieben.
nur auf das cn wäre ich nie und nimmer gekommen.also wenn ich 2 ineinader geschachtelte schleifen habe, werde ich dann ab jetzt diesen aufwand mitberechnen.
das merk ich mir.

ich habe einen weiteren code bei der ich die musterlösung auch nicht ganz verstehen kann.

also der code lautet:

int rekursion1(int n){
if(n == 0)
   return 1;
     int sum = 1;
 while(sum < n){
 sum = sum * 2;
}
return n * rekursion1(n/2) + sum
}

die musterlösung lautet:

T(n) = T(n/2) + c1*log(n) + c2

ich kann mir das log(n) nicht erklären. woher kommt das?

Bashar

pac89 schrieb:

ich kann mir das log(n) nicht erklären. woher kommt das?

Von hier:

int sum = 1;
while(sum < n){
  sum = sum * 2;
}

pac89

ok, ich versuch mal das zu erklären, was ich mir bis jetzt aufgeschrieben habe. ich will ja wenn möglich selber drauf kommen.
ist es wegen der rechnung :

n=2^x wobei x die anzahl der durchläufe ist. denn wenn ich auf beiden seiten log() rechne dann folgt daraus:

log(n) = x

ist es deshalb?

ich hab mir dazu zusätzlich ne tabelle gezeichnet. als bsp für n habe ich 8 genommen. also n=8. nach dreimaligem durchlaufen der schleife war die schleifenbedingung nicht mehr gegeben. denn log(8) = 3 , wobei es sich hier natürlich um die basis 2 handelt. ist das richtig so?
ach ja, ich habe 2 hoch x genommen, weil man ja, immer mit der 2 multipliziiert...und so weiter. das wollte ich noch hinzufügen.

pac89

ist das so korrekt, was ich da oben geschrieben habe?

Michael E.

Ja.

okay, danke....,)