"Laufzeitberechnung" eines Programmes?

[-horn-]

moien,

ich hab mal eine frage an eich informatikstudenten und hauptberuflichen programmierer.
ich würde mal gerne vorher abschätzen können, wie lange ein programm laufen wird und das nur anhand der "codemenge" und was dort gemacht wird.

es geht mir nicht wirklich darum genau auf die ms genau die echte laufzeit zu wissen, sondern ich würde gerne halt den einen code mit einem anderen code, der die selbe aufgabe erfüllt vergleichen können.

also mal ganz plakativ könnte man ja zb 2^2 einfach berechnen durch 2*2 oder über Math.pow(2,2) machen lassen, nur was wäre dann zb schneller?

ich hätte gerne schon vorher eine ahnung, was schneller wäre um gleich den code daraufhin auszurichten. da wird es doch sicherlich etwas geben, um sowas zu berechnen, oder?

grüße, Andreas

 

[Marco13]

Im allgemeinen gilt grob

Additionen/Subtraktionen/Bitoperationen/Vergleiche < Multiplikationen < Divisionen

d.h. die ersten Operationen sind relativ billig, und nach hinten wird's immer teurer. Das weiß aber auch der Compiler. Wenn du irgendwo schreibst
int x = 2 * y;
dann wird der Compiler da ggf. ein
int x = y + y;
draus machen.

Trozdem sind das Hauptproblem in den seltensten Fällen ein paar überflüssige Multiplikationen, sondern eher ineffiziente Algorithmen, und ein paar lustig-flockige "parseInt", "toString", "Collections.sort" und sonstige Aufrufe, die zwar "kurz und einfach" aussehen, aber u.U. SEHR viel Zeit fressen können.

Für konkretere Antworten wirst du konkretere Fragen stellen müssen

 

[Wildcard]

Suchst du etwas wie das O-Kalkül?

 

[Jens87]

Laufzeit anhand der Codemenge zu bestimmen wird wohl denke ich so gut wie unmöglich sein, da deine Laufzeit immer von den Eingangsgrößen abhängig sein wird. Sieht man schön z.b. bei den Fibonacci Zahlen. Algorithmen ändern ihre effizenz auch abhängig von den Eingangsgrößen. Schulmultiplikation ist beispielsweise schneller als Karatsuba aber nur wenn es um kleine Zahlen geht. Am simpelsten wirst du deine Laufzeit ermitteln können wenn du auf der untersten Ebene die Operationen zählst. Ansonsten wird dir das O-Kalkül weiterhelfen.

 

[faetzminator]

Jens87, für das verwendet man Variablen wie n, m, ... so hat z.B. Quicksort ein Worst Case von O(n^2) und Best Case von O(n * log(n)) bei bester Wahl des Pivotelements. n steht dabei für die Anzahl Elemente. Die konkrete Laufzeit ist völlig irrelevant. Es geht rein um den Vergleich, bei wie grossem n welcher Algo der schnellere ist.

 

[Ensign]

Das ist für den allgemeinen Fall unlösbar, siehe Halteproblem. Das heißt aber nicht, dass es für den spezialfall nicht machbar ist. Man müsst im Prinzip versuchen, immer mehr Transformationsregeln einzubauen damit immer größere Klassen von Programmen analysiert werden können.