Aufwand von Java-Programmen (Komplexität)

Deepthroat

Mitglied
Thread Starter
Mitglied seit
29.09.2006
Beiträge
139
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?

Code:
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

Aktives Mitglied
Mitglied seit
17.09.2005
Beiträge
3.400
Fiese Einrückungen. Wieviele Zeichen sind das? 8?
 

Dalgliesh

Mitglied
Mitglied seit
12.10.2008
Beiträge
972
Hä? Frage 1: Was hat das mit Java zu tun? Frage 2: Was hast Du da gemacht? Der Aufwand von loop2(n) 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 (n). Oder Omega (n) oder wie auch immer Du das schreibst.
 

Deepthroat

Mitglied
Thread Starter
Mitglied seit
29.09.2006
Beiträge
139
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? :confused:

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

Dalgliesh

Mitglied
Mitglied seit
12.10.2008
Beiträge
972
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

Mitglied
Mitglied seit
12.10.2008
Beiträge
972
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...
 
Oben