gibt es einen Standard zur Bestimmung des Aufwand von Algorithmen?

Gast #3351775
Lesenswert?

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
#3351800
Lesenswert?

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.
Gast #3351816
Lesenswert?

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.
#3351856
Lesenswert?

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).

Antwort schreiben

Bitte melde dich an, um einen Beitrag zu schreiben.

oder

Mit Google-Account einloggen

Die Registrierung ist kostenlos und dauert nur eine Minute.

Jetzt registrieren