asymptotische Zeitkomplexität < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:59 Di 24.03.2009 | | Autor: | Klemme |
| Aufgabe | Bestimmen Sie die asymptotische Zeitkomplexität der Programme
a) int foo (int n) { // n > 0
if (n = = 0)
return 1;
else
return 2 * foo (n/2);
}
b) // s ist ein Array mit n Elementen (n > 0)//
void bar (int s [], int n){ //}
int i, j, m, t;
for (i=0; i<n;i++) { //}
m= i;
for ( j= i+1; j<n; j++){ //}
if ( s[j]< s [m])
m=j; //{
}
t= s[i];
s[i]=s[m];
s[m]=t; //{
}
for (i=0; j<n; j++)
printf ("%d", s[j];
printf ("n"); //{
} |
Hallo,
Ich musste den Programmtext um //{ bzw. //} erweitern, da es ansonsten Fehlermeldungen gab, das diese Klammern nur paarweise auftreten dürfen.
zu a)
ich denke die Komplexität liegt hier in [mm] T(n)\in \odot [/mm] (n), da die if anweisung nur einmal ausgeführt wird
[mm] (\odot [/mm] soll hier Theta sein)
zu b)
Hier bin ich mir gar nicht sicher. [mm] T(n)\in \odot (n^{2}), [/mm] da die beiden for-Schleifen ineinander geschachtelt sind.
Es wäre nett, wenn sich das jemand mal anschauen und eventuell verbessern würde.
LG
Klemme
|
|
| |
|
> Bestimmen Sie die asymptotische Zeitkomplexität der
> Programme
>
> a) int foo (int n) { // n > 0
> if (n = = 0)
> return 1;
> else
> return 2 * foo(n/2);
> }
> Ich musste den Programmtext um //{ bzw. //} erweitern, da es ansonsten Fehlermeldungen gab, das diese Klammern nur paarweise auftreten dürfen.
Du kannst statt dessen den Code in [code]...[/code] Tags einbetten: dann liefert Dir das System sogar noch kostenlos Zeilennummern dazu.
>
> zu a)
> ich denke die Komplexität liegt hier in [mm]T(n)\in \Theta[/mm] (n), da die if anweisung nur einmal ausgeführt wird.
Du hast wohl übersehen, dass der else-Zweig einen rekustiven Aufruf von foo() mit dem Argument n/2 enthält. Wie oft musst Du ein $n$ mit $|n|>0$ halbieren, bis Du auf $n=0$ bist uns somit die rekursive Verschachtelung abbrechen kann? Doch eher [mm] $\log_2(|n|)$ [/mm] mal. Damit hätte man schon eher eine Zeitkomplexität von [mm] $\Theta\big(\log(n)\big)$.
[/mm]
Bemerkung: Wenn Du [mm] $\Theta$ [/mm] schreiben willst, dann schreibe einfach \Theta.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:14 Do 26.03.2009 | | Autor: | Klemme |
> Du kannst statt dessen den Code in
> [code]...[/code] Tags einbetten: dann liefert
> Dir das System sogar noch kostenlos Zeilennummern dazu.
Danke ^^ Das ist wirklich praktisch
> Du hast wohl übersehen, dass der else-Zweig einen
> rekustiven Aufruf von foo() mit dem Argument n/2 enthält.
Ja hab ich übersehen.
> Bemerkung: Wenn Du [mm]\Theta[/mm] schreiben willst, dann schreibe
> einfach [mm][code]\Theta[/code].[/mm]
Und nochmal danke.
LG
Klemme
|
|
|
| |
|
> Bestimmen Sie die asymptotische Zeitkomplexität der
> Programme
>
<snip/>
> b) // s ist ein Array mit n Elementen (n > 0)//
| 1: |
| | 2: | void bar (int s [], int n){
| | 3: | int i, j, m, t;
| | 4: | for (i=0; i<n;i++) {
| | 5: | m= i;
| | 6: | for ( j= i+1; j<n; j++){
| | 7: | if ( s[j]< s [m])
| | 8: | m=j;
| | 9: | }
| | 10: | t = s[i];
| | 11: | s[i]=s[m];
| | 12: | s[m]=t;
| | 13: | }[/i][/i]
| | 14: | for (i=0; j<n; j++)
| | 15: | printf ("%d", s[j];
| | 16: | printf ("n");
| | 17: | }
|
> zu b)
> Hier bin ich mir gar nicht sicher. [mm]T(n)\in \Theta(n^{2}),[/mm] da die beiden for-Schleifen ineinander geschachtelt sind.
Zwar sind die beiden for-Schleifen ineinander verschachtelt, aber die innere Schleife startet in Abhängigkeit vom Wert der Laufvariablen der äusseren Schleife bei $i+1$ und macht daher jeweils nur $(n-1)-(i+1)+1=n-1-i$ Iterationen.
Insgesamt erhält man
[mm]\sum_{i=0}^{n-1}\left(\sum_{j=i+1}^{n-1} 1\right)=\sum_{i=0}^{n-1}(n-1-i)=\sum_{i=0}^{n-1}(n-1)-\sum_{i=0}^{n-1}1=n(n-1)-\frac{n(n-1)}{2}=\frac{n(n-1)}{2}[/mm]
Also möchte ich einmal behaupten, dass es sich um einen Fall von [mm] $\Theta\big(n(n-1)\big)$ [/mm] handelt, was nicht dasselbe ist wie [mm] $\Theta(n^2)$.
[/mm]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:38 Do 26.03.2009 | | Autor: | Klemme |
Ok. Danke. Also kann ichs mir doch nicht so einfach machen. Deine Antwort hat mir auf jeden Fall sehr weitergeholfen.
LG
Klemme
|
|
|
|
