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

Informatiker Board » Themengebiete » Praktische Informatik » Algorithmen » Laufzeitabschätzung Theta Notation » Antwort erstellen » Hallo Gast [Anmelden|Registrieren]

Antwort erstellen
Benutzername: (du bist nicht eingeloggt!)
Thema:
Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

Smilies: 21 von 33
smileWinkDaumen hoch
verwirrtAugenzwinkerngeschockt
Mit ZungeGottunglücklich
Forum Kloppebösegroßes Grinsen
TanzentraurigProst
TeufelSpamWillkommen
LehrerLOL HammerZunge raus
Hilfe 
aktuellen Tag schließen
alle Tags schließen
fettgedruckter Textkursiver Textunterstrichener Text zentrierter Text Hyperlink einfügenE-Mail-Adresse einfügenBild einfügen Zitat einfügenListe erstellen CODE einfügenPHP CODE farbig hervorheben
Spamschutz:
Text aus Bild eingeben
Spamschutz

Die letzten 5 Beiträge
potu1304

Leider doch. So steht es da...

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

eulerscheZahl

In Zeile 8 und 9 wird i zwei mal definiert, da macht der Compiler nicht mit. So kann der Code nicht richtig sein.
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
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
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