hallo, gibt es Methoden mit denen man den Aufwand zum Lösen eines Algorithmus bestimmen kann? bzw. einen Standard zur Beschreibung des Aufwands? Zum Beispiel hab ich ein Programm das 2000 Additionen, 4000 Multiplikationen und 1000 Divisionen durchführt. Je nach Soft- und Hardware wird die Ausführung des Codes schneller oder langsamer gehen. Gibts sowas wie; eine Additionen hat die Komplexität von 1 ,Multiplikationen von 3 und Divisionen von 5 daraus ergibt sich mein Aufwand zum lösen zu 95000. So könnte ich das mit anderen Programmen vergleichen. Da aber vermutlich die Komplexität wider von Soft- und Hardware abgehängt ist so was aber vermutlich schwierig
Typisches Benchmarkproblem, einige tausend Randbedingungen in eine Zahl zu quetschen... Deswegen erfindet jeder seinen eigenen. Die Theoretiker haben die O-Notation. Die zählt aber nur in Abhängigkeit von der Eingangsmenge und eliminiert alle Konstanten und linearen Faktoren. Die DSPler haben die MACs. Multiply-and-Accumulate, also einmal MUL + einmal Addition, weil sich Filter&Co in dem Bereich gut darauf zurückführen lassen. Die High-Performance-Computing-Leute zählen entweder Linpack (im Rest der Welt ungefähr so sinnvoll wie ein Ningi) oder FLOPs. Allerdings ist die FPU-Addition aufwendiger als die Multiplikation, und die Division/sqrt dagegen wiederum schnarchlahm. Am ehrlichsten wäre folgende Auflistung, damit kann's jeder selbst abschätzen: a ADD/SUB (n bit int/float) b MUL (n*n->m bit) c DIV d Speicherzugriffe (lesend) e Speicherzugriffe (schreibend) d/e sollte man nicht vergessen. Bei High-Performance-Anwendungen ist meistens der Speicher der Flaschenhals, nicht die FPU.
Natürlich gib es, vor allem im Bereich der "industriellen" Computertechnik, Möglichkeiten den Aufwand abzuschätzen. Normalerweise geht das aber nur auf einem Rechner bzw. Rechnerlinie und nicht zwischen völlig verschiedenen Rechnern bzw. Architekturen. Sitzt Du z.B. in der chemischen Industrie, und Du brauchst eine neue Anlage, so wirst Du Dich zwar freuen, wenn die eine Firma die Rechner zum halben Preis anbietet während die andere fast das Doppelte verlangt. Deine Mundwinkel gehen aber schnell wieder runter, wenn sich dann herausstellt, dass noch soundso viel Geld nötig wird um "Anpassungen" an der Steuerung durchzuführen. Umgekehrt ist Firma Nummer zwei, so dass öfter passiert, bald pleite. Es gibt auch Benchmark-Programme, deren Ergebnisse eignen sich aber oft nur für den Prospekt. Nach dem Motto: Die Testaufgabe wurde 12% schneller gelöst als mit einem anderen Rechner. Wird aber eine andere, als Deine Aufgabe zur Grundlage genommen, so werden die Zeiten schnell fragwürdig.
O-Notation bzw. Landau-Notation wurden schon genannt. Der "Rest" hängt vom Kontext ab. Geht's um die Laufzeit-Komplexität sagt bspw. O(n²) das die Laufzeit in Abhängigkeit der Datenmenge n quadratisch wächst für n gegen unendlich. Das "Problem" bei dieser Notation ist, dass sie nicht unbedingt etwas über den konkreten Anwendungsfall aussagt. Beispiel: Zwei Algorithmen die dasselbe Problem lösen, einer braucht die Zeit T1(n) = n² + 10000, ein anderer T2(n) = n² + 10 n, beide wären O(n²). T1 aber für Datenmengen > 1000 schneller (der Speicherverbrauch müsste noch gesondert betrachtet werden...) Angegeben wird die Zeitkomplexität immer in Bezug auf ein bestimmtes Maschinenmodell, meist die Registermaschine. Die Zeit pro Befehl ist konstant O(1).
Vielen dank! das Hilft mir auf jeden Fall weiter.
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.