Laufzeitabschätzung Theta Notation

Neue Frage »

Auf diesen Beitrag antworten »
potu1304 Laufzeitabschätzung Theta Notation

Hallo!

Ich hänge derzeit bei Laufzeitberechnung von Programmen. Mastertheorem verstehe ich von der Theorie, komme aber nicht auf a,b und c. Auch die Theta Notation verstehe ich deshalb nicht, weil ich einfach nit drauf komme, wann O(n) oder O(log n) usw.

Z.B. dieses Beispiel:

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
void g(int n) {
  if(n==0) return;
  for (int i=2; i<3*n; ++i);
  g(n/2);
}
void h(int n, int digit) {
  if (n==0) return;
  for (int i=0; i<n; ++i)
    for (int i=n; i>0; i-=3);
  for (int i=0; i<digit; ++i)  h(n/3, digit);
}

digit hat den Wert 10.
Hier soll ich sowohl für g als auch für h die Laufzeiot abschätzen in Theta Notation. Wie gehe ich da vor?
Danke wenn mir hier jemand Helfen kann! smile

LG
 
Auf diesen Beitrag antworten »
ed209

1. Was meinst du mit a,b und c?

2. Ganz wichtig: We habt ihr Theta definiert?

3. Kannst Du den code einruecken und bist Du dir 100% sicher, dass du den Code richtig abgetippt hast?

4. Kannst Du informell beschreiben wie g funktioniert und was es tut?

Gruss,
ED209

PS: Ich gehe mal davon aus, dass Optmierungen durch den Compiler keine Rolle spielen Augenzwinkern
Auf diesen Beitrag antworten »
potu1304

1. Bei Mastertheorem haben wir es wie folgt definiert:
T(n) = aT(n/b) + f(n), wobei a >= 1, b > 1 und f(n) ist eine gegebene Funktion

2. Theta-Notation:
Das Laufzeitverhalten ist Theta(n) falls gilt: f(n)=O(n) und f(n)=Omega(n) (beschreibt das Laufzeitverhalten exakt)

Dazu die Big-O-Notation: Eine Funktion f(n) heißt von der Ordnung O(g(n)), wenn zwei Konstanten c0und n0 existieren, sodass f(n) <=c0g(n) für alle n > n0.

Und die Big-Omega-Notation: Eine Funktion f(n) heißt von der Ordnung Omega(g(n)), wenn zwei Konstanten c0 und n0 existieren, sodass f(n) >=c0g(n) für alle n > n0.

3. Ja habe den Code kopiert und nochmal geschaut ob alles passt.

4. Kann ich schwer sagen. Wenn n 0 wäre wirde es gleich nach dem ersten if aufhören. Wenn n>1 ist kommt es auf jedenfall zur for Schleife. Nehmen wir an n = 1 dann wird die for Schleife einmal durchlaufen und somit nochmal g mit n = 1/2 aufgerufen. Da n ein int ist wird es zu 0 und stoppt dann wieder beim if.
Hoffe mal das da mein Gedankenweg richtig ist.

Zu PS: Ja das hat nicht mit Kompiler zu tun, haben den Code auf Papier stehen und müssen die Laufzeitabschätzung durchführen, daher ist es wohl auch nicht wichtig, ob es einen Sinn ergibt, was das Programm macht smile

LG
Auf diesen Beitrag antworten »
eulerscheZahl

In Zeile 8 und 9 wird i zwei mal definiert, da macht der Compiler nicht mit. So kann der Code nicht richtig sein.
 
Auf diesen Beitrag antworten »
potu1304

Leider doch. So steht es da...
 
Neue Frage »
Antworten »


Verwandte Themen

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