Laufzeit eines Algorithmus bestimmen

paco89

Bekanntes Mitglied
hi,

Java:
int berechne (int n, int k){

	if(n==0){
	return k;
	}

	int value = berechne (n/3, k);

	if(n<42){
	
	for (int i = 0; i<k*k; i++){
	value +=i*n;
	value += berechne(n/3,k) +2 ;
	}
	else{
	for(int i = 0 ; i<n; i++){
		value += i*n;
		value += 3*berechne(n/3, k) + 3;
	}
	}
	}
	return value;
}


davon habe ich auch die musterlösung (siehe Musterlösung). allerdings verstehe ich da nicht woher das "n" im letzten fall T(n)= 2T(n/3) + n + c kommt. ich hatte nämlich nur T(n)= 2T(n/3) + c .
 

Anhänge

  • Musterlösung.png
    Musterlösung.png
    51,3 KB · Aufrufe: 50
S

SlaterB

Gast
die Schleife in Zeile 18 läuft doch n mal, da kann man das n schon irgendwie aufnehmen,
zumal das im Lösungstext auch ziemlich klar begründet wird?

genau 2x T(n/3) verstehe ich wiederum nicht,
zwar taucht berechne(n/3, k) genau 2x in den betrachteten Code-Abschnitten auf, aber in der Schleife wird es doch n-mal berechnet..

T(n)= n * T(n/3) + c .
schon eher, vielleicht immer noch + n, sonst kürzt sich das in der Auflösung alles weg wenn nur noch konstant c da ist..

berechne(n/3, k) könnte man schließlich auch einmalig vorberechnen, dann wäre es nur noch 1x statt 2x?
wie man sieht bringe ich eher mehr Fragen als Antworten hinein ;)
 

Neue Themen


Oben