Asymptotischer Rechenaufwand < Sonstige < Schule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:33 So 23.01.2011 | | Autor: | vivi |
Hallo allesamt,
ich wollte fragen, wie man eigentlich an einem Code den asymptotischen Rechenaufwand (hier: Anzahl der Multiplikationen) einer Rekursion "ablesen" kann?
Bsp.: static int methode(int n){
if(n<=0){return 1;}
else{
int s =1;
[b]for(int i=0;i<n;i++)
{
s*=methode(n-1);
}
return s;
}
}
Ich habe mir einen "Baum" aufgemalt für n=4, wobei methode(4)
1*methode(3)*methode(3)*methode(3)
rechnet. Meine erste Ebene des Baumes hätte dann quasi 4 Elemente (Multiplikationen). Dann verzweigt sich mein Baum weiter, pro methode(3) werden nochmal 3 Multiplikationen ausgeführt und wenn ich den Baum so weiterführe, komme ich in der untersten Ebene auf 24 Elemente, also n! Multiplikationen und mein Aufwand wäre O(n!).
Allerdings kommt mir diese Baummethode total primitiv vor, ich weiß noch nicht mal, ob die Vorgehensweise stimmt und wann ich nun ALLE Elemente (also von allen Ebenen, dann hätte ich WEIT über 24) zusammenzählen soll oder ob ich nur die Elemente der untersten Ebene betrachten muss. Kann mir jemand vielleicht das Verfahren zur Bestimmung der Komplexität kurz erklären?
Vielen Dank,
Vivi
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:08 So 23.01.2011 | | Autor: | felixf |
Moin vivi!
> Hallo allesamt,
>
> ich wollte fragen, wie man eigentlich an einem Code den
> asymptotischen Rechenaufwand (hier: Anzahl der
> Multiplikationen) einer Rekursion "ablesen" kann?
>
> Bsp.: static int methode(int n){
> if(n<=0){return 1;}
> else{
> int s =1;
> for(int i=0;i<n;i++)
> {
> s*=methode(n-1);
> }
> return s;
> }
> }
>
> Ich habe mir einen "Baum" aufgemalt für n=4, wobei
> methode(4)
>
> 1*methode(3)*methode(3)*methode(3)
>
> rechnet. Meine erste Ebene des Baumes hätte dann quasi 4
> Elemente (Multiplikationen). Dann verzweigt sich mein Baum
> weiter, pro methode(3) werden nochmal 3 Multiplikationen
> ausgeführt und wenn ich den Baum so weiterführe, komme
> ich in der untersten Ebene auf 24 Elemente, also n!
> Multiplikationen und mein Aufwand wäre O(n!).
>
> Allerdings kommt mir diese Baummethode total primitiv vor,
> ich weiß noch nicht mal, ob die Vorgehensweise stimmt und
> wann ich nun ALLE Elemente (also von allen Ebenen, dann
> hätte ich WEIT über 24) zusammenzählen soll oder ob ich
> nur die Elemente der untersten Ebene betrachten muss. Kann
> mir jemand vielleicht das Verfahren zur Bestimmung der
> Komplexität kurz erklären?
So schlecht ist das, was du machst, gar nicht 
Hier kann man es etwas einfacher machen. Bei diesem Codestueck sieht man sofort, dass die asymptotische Laufzeit gleich der Anzahl der Aufrufe der methode-Funktion ist: in methode(n) wird ja einfach nur n mal methode(n - 1) aufgerufen, oder halt 1 zurueckgeliefert falls $n [mm] \le [/mm] 0$ ist.
Sei $f(n)$ die Anzahl der Aufrufe von methode, wenn man methode(n) aufruft. Dann ist die asymptotische Laufzeit gleich $O(f(n))$.
Man sieht sofort $f(0) = 1$ und $f(n) = n [mm] \cdot [/mm] f(n - 1)$.
Damit ist $f(0) = 0!$, $f(1) = 1!$, $f(2) = 2!$, und man zeigt schnell allgemein $f(n) = n!$. Damit ist die asymptotische Laufzeit $O(n!)$.
LG Felix
|
|
|
|
