Rekursionsgleichung Allgemein < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:43 Sa 11.09.2010 | | Autor: | teka |
Hallo,
ich habe eine Frage zum aufstellen von Rekursionsgleichungen für einen gegebenen Algorithmus, da ich aus der Definition nicht ganz schlau werde.
Rekursionsgleichung: [mm]T(n)=bT(n-c)+f(n)[/mm]
Also [mm]b\ge1[/mm] ist die Anzahl der rekursiv zu lösenden Unterprobleme, das ist mir klar.
[mm]c>0[/mm] zu bestimmen fällt mir schon schwerer, ich denke das mit [mm]n-c[/mm] gemeint ist inwiefern sich die Eingabe bei einem rekursiven Aufruf verändert.
(Wird also ein Algorithmus rekursiv mit [mm]n-1[/mm] aufrgerufen ist [mm]c=1[/mm] und wird ein Algorithmus dazu nochmal rekursiv mit [mm]n-2[/mm] aufgerufen muss man dann [mm]T(n-1)+T(n-2)[/mm] nehmen??)
Aber was soll [mm]f(n)[/mm] darstellen?
Aus der Definition heißt es ist der nicht rekursive Anteil der Komplexität, aber wie kann ich das denn in einer Funktion darstellen, wenn ich einen Algorithmus in Pseudocode gegeben habe?
Danke im Vorraus.
Viele Grüße
Teka
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 06:07 So 12.09.2010 | | Autor: | leduart |
Hallo
ich versteh die frage wohl nicht ganz. Im Zweifelsfall ist doch f(n) gegeben. Wenn der Alg. die Form T(n)=bT(n-c)+f(n) kannst du dagegen nicht statt T(n-c) nit T(n-1)+T(n-2) schreiben.
Beispiel T(n)=2*T(n-2)+1/n oder [mm] T(n)=0.5*T(n-1)+(-1)^n*sin(n)
[/mm]
usw.
Weil ich nicht weiss ob das ne antwort ist, lass ich die Frage offen.
Gruss leduart
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:58 Mo 13.09.2010 | | Autor: | teka |
Hallo ich nehme mal ein Beispiel um mein Problem besser darzustellen.
Gegeben sei folgender Algorithmus:
[mm]BINOMIAL(n,k)[/mm]
[mm]Input: n, k \in \IN;[/mm]
[mm]Output:\ \vektor{n \\ k};[/mm]
[mm]if\ k = 0\ then[/mm]
[mm]return \,1[/mm]
[mm]else\ if\ n < k\ then[/mm]
[mm]return\ 0[/mm]
[mm]else\ [/mm]
[mm]return\ BINOMIAL(n - 1,k - 1) + BINOMIAL(n - 1,k)[/mm]
Rekursionsgleichung: [mm]T(n)=bT(n-c)+f(n)[/mm]
Meiner Meinung nach wäre die Rekursionsgleichung hier: [mm]T(n,k)=2\ *\ T(n - 1, k - 1)[/mm]
Die gegebene Lösung ist aber [mm]T(n,k)=1\ +\ T(n - 1, k - 1) + T(n - 1, k)[/mm]
> Wenn der Alg. die Form T(n)=bT(n-c)+f(n)
> kannst du dagegen nicht statt T(n-c) nit T(n-1)+T(n-2)
> schreiben.
Wegen dem Algorithmuss oben kam bei mir die Frage auf, ob ich, wenn ein Algorithmus rekursiv mit verschiedenen Werten aufgerufen wird, das in der Rekursionsgleichung berücksichtigen muss? (So wie es oben ja gemacht wurde...)
> Hallo
> ich versteh die frage wohl nicht ganz. Im Zweifelsfall ist
> doch f(n) gegeben.
f(n) wird in der gegebenen Rekursionsgleichung ja auch nicht berücksichtigt, heißt das ich kann f(n), solange nichts anderes gegeben ist, einfach weglassen?
Was mich auch vollkommen verwirrt ist das das in der gegebenen Lösung [mm]b = 1[/mm] ist, aber da BIOMINAL doch zweimal rekursiv aufgerufen wird müsste [mm]b = 2[/mm] sein oder??
Oder ist es so das [mm]T(n - 1, k - 1) + T(n - 1, k)[/mm] schon impliziert das BIOMINAL zweimal rekursiv aufgerufen wird und deswegen da eine eins steht?
Viele Grüße
Teka
|
|
|
| |
|
Hi, darf ich mal fragen wo du diese "Schablone" her hast? (Master-Theorem?)
Ich behaupte nämlich einfach mal, dass sich nicht jede Laufzeit allgemein in der Form T(n)=bT(n-c)+f(n) schreiben lässt.
Selbst wenn das so wäre, so ist es selten ratsam mit Schablonen zu arbeiten, du solltest die Laufzeit lieber aus dem "Nichts" heraus aufstellen, indem du dich Zeile für Zeile durch den zu betrachtenden Algorithmus arbeitest.
Nun zum eigentlichen Thema:
erstmal trotzdem die Interpretation der Schablone: T(n)=bT(n-c)+f(n)
das b, wie du schon geschrieben hast, ist die Anzahl der Rekursionszweige pro Schritt.
das Problem bei der Schablone ist, dass sie nur für Algorithmen gilt, bei der alle Rekursionszweige dieselbe Laufzeit haben!!
Beispiel: wir haben irgendeine Funktion namens foo, die mit dem Parameter n gecallt wird: foo(n)
innerhalb dieser Funktion ruft sie sich zweimal selbst auf, mit einem um 2 verringerten parameter, etwa so:
public void foo(int n) {
...
if(n>0) foo(n-2);
...
blabla
...
if(n>0) foo(n-2);
return 0;
}
man hat hier also 2 Rekursionszweige und die Laufzeit von beiden Aufrufen ist gleich, da foo mit dem gleichen Paramterwert aufgerufen wird.
b wäre hier also 2
T(n)=T(n-2) + T(n-2) = 2*T(n-2)
wenn foo aber so aussieht:
public void foo(int n) {
...
if(n>0) foo(n-2);
...
blabla
...
if(n>0) foo(n-3);
return 0;
}
dann haben wir wieder zwei Rekursionszweige, aber jeder Aufruf hat eine unterschiedliche Laufzeit!
Jetzt kannst du nicht beide Aufrufe zusammenfassen und einen Faktor b davor schreiben. Dies hier ist ein Beispiel für einen Algorithmus, der sich nicht in die Schablone drücken lässt!
Beide rekursiven Aufrufe müssen seperat in die Laufzeit eingehen, z.B.:
T(n) = T(n-2) + T(n-3)
Jetzt zum f(n) der Schablone!
das f(n) bezeichnet gewissermaßen den Aufwand/die Kosten in jedem Rekursionsschritt!!!
Beispiel:
public void foo(int n) {
if(n>0) foo(n-1);
else return 0;
}
Die Kosten, die bei jedem Aufruf dieser Funktion gezahlt werden müssen, stecken in der IF-Anweisung.
Denn es muss jedesmal geprüft werden, ob n>0 ist. Dies sind konstante Kosten (es müssen zwei Zahlen verglichen werden) - egal welchen Wert n hat!
f(n) ist hier also: f(n) = 1, unabhängig von n!
es könnte auch sein, dass in dem Algorithmus eine for Schleife steckt, die von 1 bis n läuft: for(int i=0, i<n, i++)
Die Kosten, die in dieser for-Schleife stecken, stecken im i++, denn i muss in jeder Iteration um 1 erhöht werden.
wenn n = 3 ist, passiert das 3 mal, wenn n = 9 ist passiert es 9 mal.
f(n) ist hier also nicht konstant und unabhängig von n, sondern wirklich eine Funktion von n.
---------------------------------
zum Algorithmus, den du gepostet hast:
- er lässt sich nicht in die Schablone pressen
- f(n) ist dort konstant und unabhängig von n
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:44 Mo 13.09.2010 | | Autor: | teka |
Erstmal super Antwort ;)
Vielen Dank für deine Mühe!
Warum können Professoren das nicht mal so verständlich darstellen...
Diese Schablone habe ich übrigens aus unserem Script übernommen als Definition für eine Rekursionsgleichung.
Aber damit war wohl wirklich nur "eine" gemeint.
Auf jeden Fall denke ich das ich das Prinzip jetzt verstanden habe und anwenden kann.
Vielen Dank dafür!
Grüße
Teka
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:57 Mo 13.09.2010 | | Autor: | awakening |
noch ne kleine anmerkung:
was man als "Kosten" interpretiert bleibt dem Betrachter überlassen.
Du kannst deine Betrachtung z.B. auf arithmetische Operationen beziehen aber auch auf Festplattenzugriffe oder Cachezugriffe u.v.m.
Da du vermutlich gerade in der Vorlesung Datenstrukturen&Algorithmen (oder so ähnlich) bist, wird es wohl nur um arithmetische Operationen gehen.
ein Vergleich wie bei einer IF-Anweisung, z.B. n>0 ist KEINE arithmetische Operation! Läuft also in der Betrachtung nicht unter "Kosten".
In der Lösung zu deinem Algorithmus ist f(n) = 1.
Diese 1 kommt durch die Addition der Rekursionsaufrufe
return ... + ...
die IF-Anweisungen sind nicht als Kosten berücksichtigt.
Ist aber im wahrsten Sinne des Wortes "Anssichtssache" :P
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:40 Di 21.09.2010 | | Autor: | awakening |
muss noch etwas berichtigen.
das i++ in einer for-schleife wird afaik beim compilieren vorberechnet und in einem register abgespeichert, von daher läuft das auch nicht unter kosten...
meine beispiele waren also schlecht bis falsch gewählt, aber hoffe vom prinzip her ist es klar =D
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:28 Mo 13.09.2010 | | Autor: | awakening |
Frage beantwortet, siehe meinen anderen post
|
|
|
|
