Laufzeitfunktionsbestimmung < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Gegeben sei folgender Algorithmus:
int A(int n)
{
int i, k;
i=n;
k=0;
while(i > 0)
{
k=k+1;
i=i-3;
}
return k;
}
a) Bestimmen Sie die Werte von A und T(n) für die Werte n=-1,0,1,2,3,6,9,30.
b) Was berechnet der Algorithmus? Begründung.
c) Bestimmen Sie den Laufzeitaufwand T(n) und begründen die Aufwandsklasse des Algorithmus A.
Hinweis: Als dominante Operation wählen Sie die Anzahl der Vergleiche. |
So Hallo.
Ich hoffe, ich hab das richtige Unterforum erwischt.
Also ich hab bezüglich der obig gestellten Aufgabenstellung leider arge Probleme. Ich dachte echt ich hätte es verstanden, wie ich vorgehe bei der Bestimmung von T(n). Also bin ich dann so vorgegangen, dass ich alles was nicht vergleich war mal ignoriert habe(also wegen der dominanten Operation) und hab im endeffekt mir nur alle im while angeschaut.
Da fing das Desaster dann an. Ich hab überlegt, wie lange die Schleife läuft. Da am Ende von ihr i=i-3 gesetzt wird, dachte ich mir "Mhmmm dann muss doch bei while O(n+3) sein".
Naja hingeschrieben. dann hab ich für die andren beiden Zeilen also Setzung von K k und i jeweils O(1) angenommen. Nun bin ich erstmal ewig am Überlegen gewesen, ob ich das was in der Schleife ist nun mit der While Zeile addieren oder multiplizieren muss.
Also bin ich da gescheitert. Mein Professor hat mittlerweile die Lösungen online gestellt, aber leider typisch für ihn keinen Weg mit angegeben.
Die Lösung soll sein T(n)= (n/3)+1
Wie zum Henker kommt man dadrauf? Ich versteh das eifnach nicht. Auch wie man generell bei der Laufzeitfunktion nen Bruch drin haben kann. Leider ist mein Professor nicht wirklich gut darin zu erklären. Is echt ein netter Typ aber dazu leider nicht sonderlich gut geeignet und im Kurs konnte mir bisher auch niemand wirklich genau meinen Fehler erklären. Irgendwo muss grundlegend was falsch sein bei mir.
Die b die hab ich hinbekommen und das mit den Werten von A auch. Das war ja auch nicht sonderlich schwer.
Aber die Laufzeitfunktion amcht mir generell Probleme. Mittlerweile bekomm ich zumindest bei gegebener Funktion die Aufwandsklassen hin aber ohne Funktion kann ich glaube bei der Klausur bald auch nix ausrichten.
Wäre echt super, wenn man mir hier helfen könnte. Im Forum hab ich schon bissl geschaut und da waren teilweise ähnlcihe Fragen bei, aber leider haben die mir nicht geholfen, mein Problem zu lösen.
Freu mich auf Antworten
Liebe Grüße minni
PS: Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 09:15 Do 19.06.2014 | | Autor: | schotti |
der schleifenindex i beginnt ja mit dem startwert n und nimmt dann pro schleifendurchgang um 3 ab. im wesentlichen wird die schleife also n/3-mal durchlaufen. etwas genauer: der vergleich i > 0 fällt ceil(n/3)-mal true aus, und einmal liefert er false. wenn's nur auf die anzahl vergleiche ankommen soll, dann ist die also ceil(n/3)+1.
|
|
|
| |
|
Hi
Danke für die echt sehr schnelle Antwort 
Also warum "+1" hab ich nun echt verstanden, ist ja irwie auch logisch wie du das erklärst. Aber warum teilt man durch 3?
Ich hätte nun wirklich 3 addiert weil ja am ende wie du auch sagtest i=i-3 gerechnet wird. Hab das dann auch gemacht und war dann von der Lösung total verwirrt.
Magst du mir das bitte erklären?
Vielen dank für deine Mühe
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:15 Mo 07.07.2014 | | Autor: | felixf |
Moin!
> Danke für die echt sehr schnelle Antwort
> Also warum "+1" hab ich nun echt verstanden, ist ja irwie
> auch logisch wie du das erklärst. Aber warum teilt man
> durch 3?
> Ich hätte nun wirklich 3 addiert weil ja am ende wie du
> auch sagtest i=i-3 gerechnet wird. Hab das dann auch
> gemacht und war dann von der Lösung total verwirrt.
Es wird doch von $i$ solange 3 abgezogen, bis $i$ nicht mehr $> 0$ ist.
Wenn du wissen willst, wie oft du von einer Zahl $n$ die Zahl 3 abziehen kannst bis nichts mehr da ist (bzw. bis das Ergebnis negativ ist), dann ist das doch in etwa $n/3$, oder? :)
LG Felix
|
|
|
|
