Analyse rekursiven Codes

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....,)