Laufzeitberechnung

[iNvAsIoN]

Bei der Laufzeitbetrachtung stellt sich immer die Frage , benutzt mein Algorithmus Schleifen/ Rekursion oder keines der beiden.

Zuweisungen etc. sind Konstant d.h. sie Kosten O(1). Schleifen muessen genauer betrachtet werden, wenn sie verschachtelt sind multipliziert man die innere mit der aeusseren. Wichtig hierbei ist wie oft werden sie durchlaufen. Wenn Rekursion vorliegt ist das ganze ein bisschen schwieriger. Man muss mit einer Rekursionsgleichung arbeiten. T(n)= a*T(n/b) bei (divide und conquer algorithmen kommt hinzu + aufteilen und kombinieren)

wichtig bei Divide und Conquer Algorithmen ist die Betrachtung fuer aufteilen und Kombinieren. Wenn man zu der Erkenntnis kommt das Aufteilen und Kombinieren O(n) ist , kann man es anhand von 3 Faellen bestimmen

a<b O(n) a=b O(n*log(n)) a>b n^log_b(a) wenn es nicht n ist braucht man die Summenformel. a ist die Anzahl der Rekursionsprobleme. b ist hierbei die groesse des Problems.