Rechenzeit eines Programms bestimmen |
| 30.05.2010, 18:10 | Luisa124 | Auf diesen Beitrag antworten » |
| Rechenzeit eines Programms bestimmen Ist zwar nicht direkt Mathe, aber hat was damit zu tun ;-) Außerdem können Mathematiker ja meistens auch ein bisschen Informatik ;-) Kann mir jemand erklären, wie ich die Laufzeit / Rechenzeit eines Programms auf einer Eingabe n ermittle? Zähle ich die einzelnen RAM-/Assembler-Befehle (solche wie STORE, LOAD, etc.) und bringe die dann in Verbindung mit n (je nachdem ob die Befehle in Abhängigkeit von n laufen oder nicht) oder zähle ich nur die Anzahl der elementaren Operationen wie Addition, Subtraktion etc. aus dem Programmcode und bringe diese in Verbindung mit n? Meine Ideen: Bei erster Methode würde das im RAM ja 3 Schritte (LOAD, ADD, STORE) ausmachen, bei der Methode 2 aber nur einen. Bin grad ziemlich überfragt ... Wäre super, wenn wir schnell jemand weiterhilft! Danke! Luisa |
||
| 30.05.2010, 18:17 | wurmi86 | Auf diesen Beitrag antworten » |
| RE: Rechenzeit eines Programms bestimmen hm. nur die rechenzeit? genau uhrzeit unmittelbar vor start der programms notieren. uhrzeit nach ende des programms notieren. subtrahieren. fertsch. so hab ichs zumindest immer gemacht und ich kann mich ein bisschen daran erinnern. dass ein befehl genau 1 takt entspricht. befehle zählen. gruss wurmi |
||
| 30.05.2010, 18:18 | Airblader | Auf diesen Beitrag antworten » |
Auch interessant ist hier der wiki-Artikel. Ich bin allerdings kein Informatiker, darum halte ich mich hier zurück. air |
||
| 30.05.2010, 21:47 | plizzz | Auf diesen Beitrag antworten » |
Die genaue Aufgabenstellung wäre hilfreich, denn evtl. lässt sich aus dieser dann schließen, was genau du machen musst. Üblicherweise werden Laufzeit zumindest in der theoretischen Betrachtung in O-Notation (http://de.wikipedia.org/wiki/Landau-Symb...male_Definition) angegeben. Da so ein Wikipedia-Aritkel für den Anfang ziemlicher Overkill ist, schreibe ich es mal vereinfacht hin: Es wird die Anzahl an benötigten elementaren Rechenoperationen in Abhängigkeit der Eingabe gezählt, wobei konstante Faktoren außen vor gelassen werden. Wenn ein Algorithmus bei einer Eingabe der Größe n 2n Schritte braucht, ein anderer allerdings 7n Schritte, sind dennoch beide O(n). Insofern ist es in deinem Beispiel egal, ob du das LOAD, ADD, STORE 3x zählst oder 1x. Es ist auch (in der theoretischen Betrachtung) egal, ob du LOAD, ADD, STORE 1000x oder 1x durchführen müsst, da 1000 ein konstanter Faktor ist. Einen Unterschied macht es erst, wenn du etwas n-mal, n^2-mal, etc. durchführen musst. Das Ziel ist es natürlich auch, die Laufzeit möglichst maschinenunabhängig zu implementieren. Wie es ganz genau definiert ist, weiß ich übrigens gar nicht. Denke mal, es ist über die Anzahl Schritte definiert, die eine Turingmaschine braucht, aber das ist mehr geraten und für dich auch erstmal egal. Ich hoffe mal, dass ich etwas helfen konnte, wobei euch eigentlich genau gesagt werden sollte, wie das mit den Laufzeiten ist, wenn ihr das schon machen sollt. |
||
| 30.05.2010, 23:05 | eb47vebe | Auf diesen Beitrag antworten » |
Im Grunde kannst du auch nicht wirklich von DER Laufzeit ausgehen. Da du ja auch z.B. die Speicherkomplex noch hast. Das Sieb des Erastothenes ist zum "Primzahlenfinden" bis n sicher schneller, aber frisst dafür ordentlich Speicher was auch wieder Zeit braucht / Zugriff, etc. Also eine pauschale Antwort gibt es hier nicht, ohne das konkrete Problem. |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
