Laufzeit eines Algorithmus bestimmen

[paco89]

hi,

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 .

 

[SlaterB]

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

 

[paco89]

nein, eigentlich nicht....dass mit n als Anzahl der schleifendurchläufe, hatte ich in dem Zshg. schon gedacht.