Wie kann man die Effizienz von Algorithmen in der Informatik mathematisch beweisen?
3 Antworten
Um die Laufzeiteffizienz eines Algorithmus zu bestimmten berechnet man in der Regel dessen Big-O.
Heißt man stellt eine Formel auf, um die Anzahl der benötigten Schritte in Abhängigkeit von der Anzahl der gegebenen Elemente n zu bestimmen.
Siehe:
Ein Algorithmus ist ja eine Folge von Anweisungen. Zum Beweis der Laufzeit zerlegt man ihn in diese. Meist geht es bei der Laufzeit um die asynptotische Anzahl der Bearbeigungsschritte. Das ist dann keine feste Formel, sondern es ist eine Klasse von vielen Funktionen, welche sich für große Zahlen alle fast gleich verhalten (z.B. n^2 + 1 und 2n^2 sind beide in der Klasse Θ(n^2))
Man führt dann die Laufzeit des gesamten Algorithmus auf einfache Operationen zurück, von welchen man weiß, dass sie nur konstante Zeit benötigrn (z.B. Zugriffe auf eine Speicherstelle). Man betrachtet sich alle möglichen Eingaben des Algorithmus, und da dieser (in der Regel) deterministisch ist, kann man ermitteln, wie viele Schritte letztenendes ausgeführt werden. Meist betrachtet man den worst case, also die ungünstigste Eingabe..
Ach ja, die Laufzeit wird dann immer in Abhängigkeit von der Eingabegröße betrachtet (meist mit n bezeichnet). Was genau die Größe bezeichnet, muss man sich ggf. je nach Algorithmus anschaurn. Oft ist es die gesamte Anzahl an Elementen.
Das hängt davon ab, was unter Effizienz verstanden wird. Entsprechend lassen sich Metriken und Testverfahren bzw -rechnungen entwerfen.