Laufzeitanalyse von Programmfragment

Neue Frage »

InformaticNewB Auf diesen Beitrag antworten »
Laufzeitanalyse von Programmfragment
Meine Frage:
Hallo liebe Community,

ich bin neu im Informatikbereich und stoße gerade auf die Laufzeitanalyse.
Es ist eine Schleife gegeben, zu der wir eine Laufzeitanalyse mittels Vollständiger Induktion angeben sollen.
Mein Problem ist nun, dass ich überhaupt nicht weis wie ich anfangen soll.

Hier mal die Schleife:

int summe = 0;
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= 2^i; j++) {
summe += 1;
}
}



Meine Ideen:
Was da passiert verstehe ich soweit. Wir sollten im Voraus eine Vermutung abgeben, in welcher Laufzeitklasse dieses Programmfragment liegt.
Natürlich habe ich mich hinsichtlich der O-Notation schlau gemacht und vermute, dass es in der Laufzeitklasse O(n²) liegt.

Ich hab nur leider einfach keinen Schimmer, wie ich nun meine Vermutung mittels Vollständiger Induktion belegen kann.
Vielleicht kann mir ja einer von euch den richtigen Weg weisen.
Vielen Dank im Voraus für eure Aufmerksamkeit!
LG
HAL 9000 Auf diesen Beitrag antworten »

Kurze Frage: Was bedeutet in deiner Sprache 2^i ?

a) In der Mathematik meint man damit i.d.R. die Potenz .

b) In C/C++/Java meint es aber bitweises XOR, d.h.

.

c) Oder doch ganz was anderes?

Also was ist es nun?
InformaticNewB Auf diesen Beitrag antworten »

Hi,
also es ist die Potenz in diesem Fall gemeint.
LG
InformaticNewB Auf diesen Beitrag antworten »

Ich habe ganz vergessen den Hinweis zu dieser Aufgabe anzuegeben. Diesen habe ich als Dateianhang beigefügt.
LG
HAL 9000 Auf diesen Beitrag antworten »

Also doch a). Dann finde ich dein aber etwas verwirrend, denn das passt nicht zu a), wohl aber zu b). verwirrt


Dein "Hinweis" ist die Partialsummenformel der geometrischen Reihe, damit kannst du vereinfachen, denn das ist exakt der Wert, den deine Variable "summe" am Ende der Doppelschleife annimmt.
InformaticNewB Auf diesen Beitrag antworten »

Okay, demnach wäre es vielleicht möglich das doch Fall b gemeint ist.
Im Programmfragment steht es ebenso mit 2^i und es ist Javacode. Ich hab das dann wohl einfach als Potenz impliziert.

LG
 
 
HAL 9000 Auf diesen Beitrag antworten »

Der Hinweis bezieht sich aber auf die Potenz und somit klar auf a). Ich tippe mal drauf, dass die Aufgabenautoren auf die Potenz aus waren, aber gewisse Kenntnismängel in der Java-Syntax haben - vermutlich haben sie den Code einfach hingeschrieben, statt ihn auch mal auszuprobieren... Augenzwinkern
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »