Laufzeitabschätzung < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:43 Mo 05.07.2010 | | Autor: | matheja |
| Aufgabe | Moin Leute,
ich habe große probleme damit die Laufzeit von Programmen zu bestimmen.
Ich hoffe ihr könnt mir helfen:
Gegeben sei folgender quellcode:
| 1: | public boolean example method (V comp_value) {
| | 2: | if (value==comp_value) return true;
| | 3: | else {
| | 4: | boolean answer_left=false;
| | 5: | boolean answer_right=false;
| | 6: | if(left!=null) answer_left=left.example_method (comp_value);
| | 7: | if(right!=null) answer_right=right.example_method (comp_value);
| | 8: | if (answer_left || anser_right) return true;
| | 9: | else return false;
| | 10: | }
| | 11: | }
|
|
a) Beschreiben sie kurz was die methode example_method macht
b) Stellen sie die rekursionsgleichung für die worst-case komplexität der Methode example_method auf.Geben sie den nichtrekursiven Aufwand pro Aufruf zur vereinfachung durch eine Konstante c an, ferner sei T(0)=d für c,d element N.Ermitteln sie nachvollziehbar eine Lösung in Abhängigkeit con der Anzahl n der Knoten eines binären baumes.gehen sie zur vereinfachung von einem vollständigen baum aus, d.h [mm] n=2^k-1 [/mm] für ein k element N.
Meine Ideen:
1.Value wird mit com_value verglichen wenn die werte gleich sind wird ein true zurückgegeben
andern falls gibt die methode ein false aus
2.wenn der linke wert ungleich null ist wird comp_value answer left zurückgeben
3.wenn der rechte wert ungleich null ist wird comp_value answer recht zurückgeben
anschließend werden beide werte zurückgegeben.
mit anderen worten ich weiß nicht wirklich was die metode eigentlich macht
b) ja ich steh ich derbst im dunkeln
hier brauch ich intensive unterstützung
ich hab versucht via internet mich schlau zu machen aber leider hat da nicht viel gebfracht.
Liebe dank für eure unterstüzung
matheja
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:41 Mo 05.07.2010 | | Autor: | felixf |
Moin
> ich habe große probleme damit die Laufzeit von Programmen
> zu bestimmen.
> Ich hoffe ihr könnt mir helfen:
>
> Gegeben sei folgender quellcode:
>
> | 1: | public boolean example method (V comp_value) {
| | 2: | > if (value==comp_value) return true;
| | 3: | > else {
| | 4: | > boolean answer_left=false;
| | 5: | > boolean answer_right=false;
| | 6: | > if(left!=null) answer_left=left.example_method
| | 7: | > (comp_value);
| | 8: | > if(right!=null)
| | 9: | > answer_right=right.example_method (comp_value);
| | 10: | > if (answer_left || anser_right) return true;
| | 11: | > else return false;
| | 12: | > }
| | 13: | > }
| | 14: | > |
> a) Beschreiben sie kurz was die methode example_method
> macht
> b) Stellen sie die rekursionsgleichung für die worst-case
> komplexität der Methode example_method auf.Geben sie den
> nichtrekursiven Aufwand pro Aufruf zur vereinfachung durch
> eine Konstante c an, ferner sei T(0)=d für c,d element
> N.Ermitteln sie nachvollziehbar eine Lösung in
> Abhängigkeit con der Anzahl n der Knoten eines binären
> baumes.gehen sie zur vereinfachung von einem vollständigen
> baum aus, d.h [mm]n=2^k-1[/mm] für ein k element N.
>
> Meine Ideen:
>
> 1.Value wird mit com_value verglichen wenn die werte gleich
> sind wird ein true zurückgegeben
Das stimmt.
> andern falls gibt die methode ein false aus
Wie kommst du dadrauf?
> 2.wenn der linke wert ungleich null ist wird comp_value
> answer left zurückgeben
> 3.wenn der rechte wert ungleich null ist wird comp_value
> answer recht zurückgeben
Das ist ebenso Quark.
> anschließend werden beide werte zurückgegeben.
Versuche mal Anhand mehrerer konkreter Beispiele (die Datenstruktur, auf der du arbeitest, ist ein binaerer Baum, dessen Knoten jeweils einen Wert "value" haben, der mit dem Parameter "comp_value" verglichen wird) nachzuvollziehen, was wirklich passiert.
Und zwar Programmzeile fuer Programmzeile.
Solange bis du wirklich verstehst was passiert.
> b) ja ich steh ich derbst im dunkeln
> hier brauch ich intensive unterstützung
Solange du a) nicht hinbekommst, brauchst du b) erst gar nicht zu versuchen.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:48 Mo 19.07.2010 | | Autor: | matheja |
| Aufgabe | Hi Leute,
ich hab mich nochmal an die Laufzeit abschätzung in 0 notation versucht. |
Mein Vorschlag:
| 1: | public boolean example method (V comp_value) {
| | 2: | if (value==comp_value) return true; // 1Schritt
| | 3: | else {
| | 4: | boolean answer_left=false; // 1
| | 5: | boolean answer_right=false; //1
| | 6: | if(left!=null) answer_left=left.example_method (comp_value); //1 +1
| | 7: | if(right!=null) answer_right=right.example_method (comp_value); // 1+1
| | 8: | if (answer_left || anser_right) return true; // 1
| | 9: | else return false;
| | 10: | }
| | 11: | }
|
</task>
=> insgesamt brauch das Programm 8 schritte => Laufzeit = 0(8) ???
was meint ihr?
wenn mein Ansatz falsch ist, wie könnte ich es besser machen.
man sieht eigentlich dass das Programm eine lineare Laufziet hat, aber ich weiß nicht wie ich das besser aufschreiben kann, bzw. geschickt herleiten kann mit den gewünschnten rekursionsformeln
Danke für Rat
matheja
|
|
|
| |
|
Hallo!
Sowas wie O(8) gibt es eigentlich nicht.
Normalerweise geht es doch darum, einen gewissen Datensatz unbestimmter Größe zu bearbeiten. Die Laufzeit gibt dann an, nach welchem mathematischen Gesetz sich die LAufzeit vergrößert, wenn sich die Datenmenge vergrößert.
Das hieße in deinem Fall, was passiert, wenn man einen größeren Baum benutzt. Nimmt die Laufzeit linear zu, also O(n), nimmt sie quadratisch zu -> O(n²), oder noch anders? O(log(n))?
Es macht auch wenig Sinn, irgendwelche einzelnen Schritte zu zählen, denn du weißt nicht, wie lange der Rechner tatsächlich benötigt.
Ein "boolean answer_left=false" geht z.B. extrem schnell, das "if (value==comp_value) return true;" ist dagegen ja schon ein ganzer Haufen an Anweisungen. Oder stell dir vor, eine CPU kann nicht in Hardware multiplizieren, sondern nur addieren. Intern muß also sowas wie ne schriftliche Multiplikation ablaufen, und das dauert schon ein weilchen. Aber das siehst du dem Code einer Hochsprache nicht an. Die Aussage "8 Schritte" macht daher keinen Sinn, solange du nicht in den Maschinencode guckst und sagen kannst, wieviele Taktzyklen der Rechner dafür braucht. Es macht nur Sinn zu sagen, daß er für die doppelte Datenmenge etwa vier mal so lange braucht o.ä.
Dazu suchst du nach sich wiederholenden Programmsequenzen, also Schleifen, die über den Datensatz laufen, etc. Und du schaust, wie sich die Anzahl der Durchläufe ändert, wenn die größe des Datensatzes sich ändert.
Welcher Programmteil wird denn hier immer wieder durchlaufen? Zugegeben, es ist was spezielles, und keine Schleife!
Was genau passiert denn in den zeilen 6 und 7?
|
|
|
|
