Registrierung Kalender Mitgliederliste Teammitglieder Suche Häufig gestellte Fragen Zur Startseite

Informatiker Board » Themengebiete » Praktische Informatik » Algorithmen » Laufzeitabschätzung Theta Notation » Hallo Gast [Anmelden|Registrieren]
Letzter Beitrag | Erster ungelesener Beitrag Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen
Neues Thema erstellen Antwort erstellen
Zum Ende der Seite springen Laufzeitabschätzung Theta Notation
Autor
Beitrag « Vorheriges Thema | Nächstes Thema »
potu1304
Grünschnabel


Dabei seit: 19.09.2015
Beiträge: 4

Laufzeitabschätzung Theta Notation Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von potu1304: 20.09.2015 14:44.

19.09.2015 16:11 potu1304 ist offline Beiträge von potu1304 suchen Nehmen Sie potu1304 in Ihre Freundesliste auf
ed209
Routinier


Dabei seit: 07.09.2006
Beiträge: 324

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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
20.09.2015 13:11 ed209 ist offline E-Mail an ed209 senden Beiträge von ed209 suchen Nehmen Sie ed209 in Ihre Freundesliste auf
potu1304
Grünschnabel


Dabei seit: 19.09.2015
Beiträge: 4

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von potu1304: 20.09.2015 14:45.

20.09.2015 14:44 potu1304 ist offline Beiträge von potu1304 suchen Nehmen Sie potu1304 in Ihre Freundesliste auf
eulerscheZahl eulerscheZahl ist männlich
Foren Gott


Dabei seit: 04.01.2013
Beiträge: 2.859

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

In Zeile 8 und 9 wird i zwei mal definiert, da macht der Compiler nicht mit. So kann der Code nicht richtig sein.

__________________
Syntax Highlighting fürs Board (Link)
20.09.2015 15:46 eulerscheZahl ist offline Beiträge von eulerscheZahl suchen Nehmen Sie eulerscheZahl in Ihre Freundesliste auf
potu1304
Grünschnabel


Dabei seit: 19.09.2015
Beiträge: 4

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

Leider doch. So steht es da...

potu1304 hat dieses Bild (verkleinerte Version) angehängt:
bandicam 2015-09-20 15-48-23-715.jpg

20.09.2015 15:49 potu1304 ist offline Beiträge von potu1304 suchen Nehmen Sie potu1304 in Ihre Freundesliste auf
Baumstruktur | Brettstruktur
Gehe zu:
Neues Thema erstellen Antwort erstellen
Informatiker Board » Themengebiete » Praktische Informatik » Algorithmen » Laufzeitabschätzung Theta Notation