Du verwendest einen veralteten Browser. Es ist möglich, dass diese oder andere Websites nicht korrekt angezeigt werden. Du solltest ein Upgrade durchführen oder ein alternativer Browser verwenden.
wie berechnet man eigentlich die Laufzeit von Algirthmen?
Ich meine gut, ich weiß irgendwas mit O(n) und so weiter, aber kann man das selbst nicht auch ausrechnen?
Welche Methoden gibt es dafür?
Grundsätzlich sucht man Schranken für die Anzahl an im Algorithmus durchgeführten Elementarschritten. Wenn Du auf sehr niedriger Ebene und formal arbeiten willst, dann stellst Du eine Schrittzahlfunktion auf und beschreibt deren Wachstum mit Hilfe der Landau-Symbole (O-Notation).
Beispiel zur Bestimmung des letzten Vorkommens eines Zeichens in einem char-Array:
Java:
public int lastIndexOf(char[] txt, char c) {
int pos = txt.length - 1;
while (pos >= 0) {
if (txt[pos] == c) {
break;
}
pos--;
}
return pos;
}
Frage: wie ist die Laufzeit im schlechtesen Fall (worst case) in Abhängigkeit der Textlänge n?
Formal müsstest Du jetzt eine Schrittzahlfunktion SZ(n) aufstellen (und ggf. Korrektheit beweisen). In Zeile 2 wird die initiale Position gesetzt, macht einen Schritt. In Zeile 3 folgt ein Vergleich als weiterer Schritt, Zeile 4 ein weiterer Vergleich und damit weiterer Schritt, dann geht es weiter mit Zeile 7 (worst case), dann zurück zu 3 usw.
Bei jeder Iteration der Schleife werden also drei Schritte ausgeführt, die Schleife wird n-mal durchlaufen. Wenn die Schleife terminiert, erfolgt nochmal ein Vergleich in Zeile 3. In Zeile 9 noch ein Schritt für die Rückgabe (sofern man die zählen will), macht insgesamt SZ(n) = 1 + 3n + 1 + 1 = 3 + 3n. Die Schrittzahlfunktion wächst nicht wesentlich schneller als n, somit liegt die Laufzeit in O(n). Formal heißt das, dass positive Konstanten C und x0 existieren, so dass für alle x > x0 gilt: |SZ(x)| = |3+3x| = 3+3x ≤ Cx. Das ist z. B. für x0=2 und C=4 der Fall.
Etwas mehr an der Praxis orientiert: Zeile 1 ist konstant: O(1), Schleife in den Zeilen 3 bis 8 läuft über alle n Zeichen, in der Schleife gibt es nur konstante Laufzeiten, also liegt die Laufzeit der Schleife in O(n). Beim return passiert nix aufregendes, also O(1), macht O(1) + O(n) + O(1) = O(n).
Dann würde mir noch die Reduktion einfallen. Damit kann z. B. die untere Schranke eines Algorithmus angegeben werden, indem man ein Problem mit bekannter unterer Schranke auf das betrachtete reduziert. Damit können nicht nur einzelne Algorithmen sondern komplette Probleme behandelt werden.