Komplexität von Algos < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:46 Fr 09.01.2009 | | Autor: | Phecda |
Hi
hab ne aufgabe wo ich nicht mal ansatzweise verstehe was ich machen soll [mm] =\
[/mm]
gegeben ist die rek fkt f:
int f(int a,int b){
if (a >= b) {
return g(a);
} else {
return f(a,b-1) + f(a+1,b);
}
}
die frage ist:
berechnen sie die algorithmische komplexität der funktion f. dabei sei n = b-a der komplexitätsparameter.
Überlegen sie eine formel für T(n), die anzahl der additionen bei der berechnung von f(a,b) wobei n = b-a. Dieser aufwand ist abhängig von T(g), der anzahl der additionen in der berechnung von g. T(g) sei dabei unabhängig vom eingabeparameter von g, also eine konstante.
kann mir jmd erklären was ich machen soll?
hab schon 2 stunden skripte gelesen aber blick einfach nicht durch... sry
danke :)
lg
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 09:43 Mo 12.01.2009 | | Autor: | bazzzty |
> Hi
> hab ne aufgabe wo ich nicht mal ansatzweise verstehe was
> ich machen soll
>
> gegeben ist die rek fkt f:
>
> int f(int a,int b){
> if (a >= b) {
> return g(a);
> } else {
> return f(a,b-1) + f(a+1,b);
> }
> }
>
> die frage ist:
> berechnen sie die algorithmische komplexität der funktion
> f. dabei sei n = b-a der komplexitätsparameter.
> Überlegen sie eine formel für T(n), die anzahl der
> additionen bei der berechnung von f(a,b) wobei n = b-a.
> Dieser aufwand ist abhängig von T(g), der anzahl der
> additionen in der berechnung von g. T(g) sei dabei
> unabhängig vom eingabeparameter von g, also eine
> konstante.
>
> kann mir jmd erklären was ich machen soll?
> hab schon 2 stunden skripte gelesen aber blick einfach
> nicht durch... sry
Dass spricht ja nur für Dich, dass Du schon Skripte gelesen hast, kein Grund, sich zu entschuldigen.
Ich verstehe die Aufgabe so:
Wenn man die Funktion mit Parametern $a,b$ aufruft, dann kann man bei der Berechnung die Additionen (Subtraktionen zählen als Additionen) zählen und die als $T(a,b)$ bezeichnen. Das entspricht der Laufzeit, wenn man annimmt, dass nur Additionen Zeit kosten.
Einen wichtigen Schritt hat man schon mit der Aufgabe vorweggenommen: $T(a,b)$ hängt nicht wirklich von beiden Parametern ab, sondern ist nur von der Differenz abhängig. Es reicht also, nur $T(n)$ zu betrachten.
Die Laufzeit kann man dann auch wieder rekursiv aufschreiben:
[mm]T(n)=\begin{cases}c\cdot T(n-1)&:n>0\\ T(g)&:n\leq 0\end{cases}[/mm]
Das $c$ kannst Du Dir selbst überlegen, denke ich!
Man kann das dann auch geschlossen darstellen; ich weiß aber nicht, ob das gefragt ist.
> danke :)
> lg
|
|
|
|
