Laufzeit eines Programms berechnen.
-
Wie kann man die Laufzeit eines Programms berechnen?
In den meisten faellen steht sowas wie o(o^n)Ghost
-
Hi,
das ist keine Laufzeit, sondern die Komplexität.
Also es wird angegeben, wie oft ein bestimmter Algo durchlaufen wird.Z.B. einfachs Fall.
for (int i=0; i<X; i++) printf("Hallo, again\n");
Du siehst, dass die Zeile X mal ausgegeben wird.
Wenn du X mal verdoppelst, verdoppelt sich auch die Anzahl der Durchläufe.
Dieser 'Algo' hat also eine lineare Abhängigkeit.
-
O(n) beschreibt, wie das Zeitverhalten von z.B. der Eingangsdatenmenge abhängt. Konstante Faktoren und Konstantzeiten werden dabei vernachlässigt, das ganze dient weniger einer Zeitberechnung als einer Abschätzung der Skalierbarkeit des Algorithmus: Dauert der Algorithmus für die zehnfache Datenmenge zehnmal so lang? hudertmal so lang?
Die häufigsten Faktoren sind N (lineare Suche), log N (binäre Suche), sowie Produkte davon, die durch verschachtelte Schleifen entstehen.
-
Bei rekursiven Algorithmen gibt es feine Laufzeiten.
Nicht-primitiv rekursiv, µ-rekursuv...*ans Abi denk*
-
Was hat die Art der Rekursion mit der Laufzeitkomplexität zu tun?
-
Kann man schöner rechnen als zB O(3+4*n)
-
O(3+4*n) = O(n)
