Laufzeitberechnung < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:36 So 20.06.2010 | | Autor: | XeZZ |
| Aufgabe | Bestimmen sie die Asymptotische Laufzeit:
int h,i,j,k;
h = 0; i = 0;
while (i<n) {
h++;
i = i + h;
for (j = 1; j <= 2n; j++) {
k = n;
while (k > 0) {
k = k/2; }
}
} |
Hiho,
ich hab nen problem undzwar kann ich das Muster der äußeren Whileschleife irgendwie nicht erkennen. ich hab schon veruscht irgenwelche Summenformeln aufzustellen bin aber irgendwie dran gescheitert.
Die laufzeit der der Forschleife dürfte ja 2n sein und die der inneren while ln(n).
Kann mir bitte jemand erklären wie man auf die laufzeit der äßeren while Schleife kommt?
mfg
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:31 Mo 21.06.2010 | | Autor: | felixf |
Moin!
> Bestimmen sie die Asymptotische Laufzeit:
>
> int h,i,j,k;
> h = 0; i = 0;
> while (i<n) {
> h++;
> i = i + h;
> for (j = 1; j <= 2n; j++) {
> k = n;
> while (k > 0) {
> k = k/2; }
> }
> }
> Hiho,
>
> ich hab nen problem undzwar kann ich das Muster der
> äußeren Whileschleife irgendwie nicht erkennen. ich hab
> schon veruscht irgenwelche Summenformeln aufzustellen bin
> aber irgendwie dran gescheitert.
>
> Die laufzeit der der Forschleife dürfte ja 2n sein und die
> der inneren while ln(n).
Nein, die Laufzeit der for-Schleife ist sicher nicht $2 n$, sondern $O(2 n [mm] \log_2 [/mm] n) = O(n [mm] \log [/mm] n)$. Die Anzahl der Iterationen der for-Schleife ist $2 n$. Die Anzahl der Iterationen der inneren while-Schleife ist [mm] $\log_2 [/mm] n$, und die Laufzeit somit [mm] $O(\log [/mm] n)$.
> Kann mir bitte jemand erklären wie man auf die laufzeit
> der äßeren while Schleife kommt?
Nun, die for-Schleife haengt nicht von der aeusseren while-Schleife ab. Somit musst du "einfach nur" die Anzahl der Iterationen der aeusseren while-Schleife zaehlen. Schau dir mal folgende Tabelle an (die Werte der Variablen vor dem h++;):
[mm]\begin{tabular}{c|c} h & i \\ \hline 0 & 0 \\ 1 & 1 \\ 2 & 3 \\ 3 & 6 \\ 4 & 10 \\ 5 & 15 \\ 6 & 21 \end{tabular}[/mm]
Du siehst: $i$ hat am Anfang der Schleife den Wert $i = 0 + 1 + 2 + [mm] \dots [/mm] + h = [mm] \sum_{j=1}^h [/mm] j = [mm] \frac{h (h + 1)}{2}$ [/mm] -- diese Summenformel hast du sicher schonmal gesehen. Und $h$ ist gleich der Anzahl der Iterationen.
Jetzt ueberlege dir, wie lange [mm] $\frac{h (h + 1)}{2} [/mm] < n$ gilt.
LG Felix
|
|
|
|
