Aufwand von Java-Programmen (Komplexität)

[Deepthroat]

Hey,

ich grübel hier grad über ner Java-Aufgabe. Ich soll den exakten und asymptotischen Aufwand von Programmteilen angeben.... Könnte mir mal jemand sagen, ob ich das richtig verstanden habe, und meine Lösung für den exakten Aufwand stimmen?

loop2(n) { 				
	if (n > 0) { 				(1)	1
		loop2(n - 100); 		(1)	1
	} else if (n < 0) { 			(1)	1
		loop2(n + 1); 			(1)	1
	} 
} 



b) 

loop3(n) { 
	m = n; 					(1)	1
		while (m <= n) { 		(1)	n+1
			i = n; 			(1)	n
			while (i > 1) { 	(1)	n+1
				i = i / 2; 	(1)	n
			} 
			m = m + i; 		(1)	1
			n = n + 2; 		(1)	1
		} 

} 



c) 

loop4(n) { 					
	m = n; 					(1)	1
	i = 2 * n; 				(1)	2
		while (i > 2) { 		(1)	n+1 
			m = m + n; 		(1)	n
			i = i - 2; 		(1)	n
		} 
}

In den Klammern steht der Aufwand bei einem Durchlauf, dahinter "allgemein"...

PS: Ich hasse es...

 

[tafkas]

Fiese Einrückungen. Wieviele Zeichen sind das? 8?

 

[Dalgliesh]

Hä? Frage 1: Was hat das mit Java zu tun? Frage 2: Was hast Du da gemacht? Der Aufwand von loop2 zum Beispiel ist doch nicht 1, sondern proportional zu n. Wäre n=520, also 6 + 80, denn 6mal wird 100 abgezogen und 80mal 1 addiert. Wie Du das exakt ausdrücken willst, weiß ich nicht genau, so etwa

g (n / 100) + g (n / 100) * 100 - n für n > 0,
-n für n < 0,

wobei g (x) die kleinste ganze Zahl größer als x ist. Asymptotisch dann O . Oder Omega oder wie auch immer Du das schreibst.

 

[Deepthroat]

Danke erstmal für die Denkanstöße. Was das mit Java zu tun hat, würd ich auch gern wissen.

Zu deiner zweiten Frage:
In unserer Vorlesung wurde gesagt, dass bei 1. Initialisierungen von Variablen, 2. bei mathematischen Operationen gezählt wird. Keine Schrittzählung für reine Wertzuweisungen. Außerdem sollen rekursive Aufrufe nicht gezählt werden.

Also ergibt sich doch für loop2 ein Aufwand von 4, oder nicht?

Der für loop3 wäre nach meiner "Lösung" 4n+4.

 

[Dalgliesh]

Hm. Warum rekursive Aufrufe nicht zählen, verstehe ich nicht.

Hast Du bei loop3 nicht einen Logarithmus? i = n; while (i > 1) i = i /2; braucht doch ungefähr log2 n Schritte und nicht n?

 

[Dalgliesh]

Loop3 bricht für n > 0 nie ab, oder sehe ich das falsch? Du machst am Ende jedes Durchlaufs n um 2 größer und m um 1...