Laufzeit bestimmen in Theta-Notation
-
Hallo!
Das ist mein erster Post hier und es handelt sich auch gleich um ein Aufgabenbsp. von der Uni, falls hier solche Threads nicht erwünscht sind, lasst es mich bitte gleich wissen, dann belästige ich euch in Zukunft nur mehr mit real-life C++ Fragen
Nun zum Beispiel: ich hab folgende 3 Funktionen gegeben und soll jeweils die Laufzeit in Big-Theta-Notation bestimmen.
void eins(int n) { for (int i=3; i<n; ++i) for (int j=0; j<i; ++j) eins(n-1); }Hier komme ich auf Theta(n^3), da beide Schleifen und die Rekursion von n abhängig und verschachtelt sind.
void zwei(int n) { for (int i=1; i<n; i*=5) for (int j=n; j>0; j/=2); }Hier komme ich für beide Schleifen auf eine logarithmische Laufzeit, zusammen dann also log^2(n), bin mir aber sehr unsicher!
void drei(int n) { if (n==0) return; for (int i=0; i<12; ++i) drei(n/2, 12); }Hier kann man das Mastertheorem anwenden, a=12 b=2 c=0, daraus folgt c < logb(a) und somit eine Laufzeit von Theta(n^log2(12)).
lg, Jay
-
Sieht alles gut aus. Bist Du sicher, dass as genügt? Unter "bestimmen" hätte ich mir was ausführlicheres Vorgestellt als nur angeben der laufzeiten.
-
Danke für deine Antwort!
Laufzeit angeben + ein wenig erklären wie man dazu kommt reicht in meinem Fall völlig aus.
-
Hier komme ich auf Theta(n^3), da beide Schleifen und die Rekursion von n abhängig und verschachtelt sind.
Geht das genauer. Ich habe (n!)^2 raus ...
n^2 * (n-1)^2 * (n-2)^2 * ...
-
Ich löse die Rekurrenz T(n-1) so auf:
T(n) = T(n-1) = T(n-1) + 1 = T(n-2) + 1 + 1 = 1 + ... + 1 + 1 = n
-
Und ich: wegen den Schleifen und weil weil eins(n-1) in der Schleife steht.
eins(n) = n^2 * eins(n-1)
eins(n) = n^2 * (n-1)^2 * eins(n-2)
eins(n) = n^2 * (n-1)^2 * (n-2)^2 * eins(n-3)
...
keine Ahnung, wo du das +1 her hast.
-
das +1 ist natürlich falsch (hatte es von einem anderen bsp. wo es in der rekursion eine abbruchbedingung mit return 1; gibt)
Theta(n!)^2 ist somit richtig.
danke
