Laufzeit rekursiver Methoden < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Eure Aufgabe ist es, im folgenden einen besonders effizienten Algorithmus zum berechnen für [mm] x^n [/mm] anzugeben. Dabei soll x [mm] \in \IR [/mm] und n [mm] \in \IN [/mm] sein.
Folgende Gleichheit soll euch einen Hinweis auf das Funktionsprinzip geben:
$ [mm] x^9 [/mm] = x [mm] \cdot x^4 \cdot x^4 [/mm] $.
a)Entwickelt einen rekursiven Algorithmus in JAVA, der die Potenz [mm] x^n [/mm] möglichst effizient berechnet, das heißt die Laufzeit soll c [mm] \cdot \log_2{n} [/mm] für eine natürliche Zahl c sein. Der Algorithmus darf keine Schleife enthalten und auch nicht Math.pow verwenden.
Beweist seine Laufzeit, d.h. insbesondere findet ein passendes c.
Hinweis: Um die Laufzeit zu bestimmen, zählt ihr die Anzahl der rekursiven Aufrufe des Algorithmus. |
So. Frisch ans Werk, die Methode ist schnell implementiert.
public static long pow(int x, int y){
[mm] \quad [/mm] if (x == 0 || x == 1 || y == 1) return x;
[mm] \quad [/mm] if (y == 0) return 1;
[mm] \quad [/mm] long tmp = pow(x,y/2);
[mm] \quad [/mm] if (y % 2 == 0) return tmp * tmp;
[mm] \quad [/mm] else return x*tmp*tmp;
}
Nun zum eigentlichen Problem. Dem Beweis der Laufzeit.
Wenn T die Anzahl der rekursiven Aufrufe ist, dann bin ich der Meinung, dass ganz allgemein gilt:
$ T(x, n) [mm] \le \log_2{n} \quad \forall [/mm] n [mm] \in \IN [/mm] $
Da es für alle Beispiel die ich mir gesucht habe, geklappt habt. Nun hab ich mir gedacht, beweis ich das einfach über vollständige Induktion.
Dabei lauf ich allerdings immer wieder in eine Sackgasse.
$ T(x, n+1) = T(x, [mm] \left \lfloor \frac{n+1}{2} \right \rfloor) [/mm] + 1 $
Die Gleichheit resultiert ja aus dem Java-Code.
Aber nun komm ich nicht ganz weiter. Irgendwie muss ich zeigen.
$ T(x, n+1) [mm] \le \log_2{(n+1)} \quad \forall [/mm] n [mm] \in \IN [/mm] $
Aber da komm ich Partou nicht hin.
Hat jemand eine Idee, einen Vorschlag? Mach ich was falsch? Vielen Dank schon mal im Vorraus.
Gruß André
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 01:20 Mi 26.01.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
