Fkt.berechnung in gewiss. Zeit < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | | We define the function [mm] f:\IN\to\IN [/mm] as follows: f(1)=2 and [mm] f(i+1)=2^{f(i)^{1.2}}. [/mm] Note that given n, we can easily find in [mm] O(n^{1.5}) [/mm] time the number i such that n is sandwiched between f(i) and f(i+1). |
Obiger Text entstammt einem Lehrbuch. Leider finde ich die Aussage, wie so oft, entgegen der Behauptung der Autoren gar nicht so trivial. Meine Frage wäre daher, wie man sich davon überzeugen kann, dass man ein solches i eben in Zeit [mm] O(n^{1,5}) [/mm] finden kann.
Ich würde ja gerne belegen, dass ich schon selbst lange darüber nachgedacht habe. Aber ich bin nicht mals auf einen Ansatz gekommen, der in die richtige Richtung führen würde. Das einzige, was man evtl. als Ansatz werten könnte, ist folgendes: Da die Funktion rekursiv definiert ist, müssen wir wahrscheinlich f(1), f(2), f(3), ... , f(i) ausrechnen, und zwar so lange, bis f(i) [mm] \ge [/mm] n. Aber wieso dauern diese Berechnungen zusammen nun weniger als [mm] O(n^{1,5}) [/mm] Zeit?
Die Frage wurde sonst nirgends gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:43 Fr 14.02.2014 | | Autor: | felixf |
Moin,
> We define the function [mm]f:\IN\to\IN[/mm] as follows: f(1)=2 and
> [mm]f(i+1)=2^{f(i)^{1.2}}.[/mm] Note that given n, we can easily
muss da nicht irgendwie gerundet werden, so dass eine natuerliche Zahl herauskommt?
> find in [mm]O(n^{1.5})[/mm] time the number i such that n is
> sandwiched between f(i) and f(i+1).
>
> Obiger Text entstammt einem Lehrbuch. Leider finde ich die
> Aussage, wie so oft, entgegen der Behauptung der Autoren
> gar nicht so trivial. Meine Frage wäre daher, wie man sich
> davon überzeugen kann, dass man ein solches i eben in Zeit
> [mm]O(n^{1,5})[/mm] finden kann.
>
> Ich würde ja gerne belegen, dass ich schon selbst lange
> darüber nachgedacht habe. Aber ich bin nicht mals auf
> einen Ansatz gekommen, der in die richtige Richtung führen
> würde. Das einzige, was man evtl. als Ansatz werten
> könnte, ist folgendes: Da die Funktion rekursiv definiert
> ist, müssen wir wahrscheinlich f(1), f(2), f(3), ... ,
> f(i) ausrechnen, und zwar so lange, bis f(i) [mm]\ge[/mm] n. Aber
> wieso dauern diese Berechnungen zusammen nun weniger als
> [mm]O(n^{1,5})[/mm] Zeit?
Die Folge $f(i)$ waechst sehr stark, so dass du sehr schnell $f(i) [mm] \ge [/mm] n$ haben wirst. Du solltest abschaetzen, wieviele Schritte du hoechstens brauchst, und dann den Aufwand zum Berechnen der $f(i)$ darunter abschaetzen. Dazu musst du wissen, wieviel das Auswerten der Funktion $x [mm] \mapsto 2^{x^{1.2}}$ [/mm] kostet.
LG Felix
|
|
|
| |
|
So weit, so klar. Leider weiß ich allen drei Schritten nicht, wie ich es tun soll.
1. Anzahl der Schritte: Hier ist mir die rekursive Formulierung im Weg. Wäre die Funktion z.B. einfach als [mm] 2^{i^{1,2}} [/mm] definiert, so wäre die Anzahl der Schritte klar: [mm] 2^{i^{1,2}}\ge n\gdw i\ge\wurzel[1,2]{log_{2}n}. [/mm] Aber bei der rekursiven Funktion stehe ich auf dem Schlauch.
2. Aufwand für eine [mm] 2^{i^{1,2}} [/mm] Berechnung: Auch hier komme ich nicht wirklich weiter. Wie lange dauert die Berechnung einer Funktion? Da habe ich überhaupt keine Intuition für. Auch schon für wesentlich einfachere Beispiele wie [mm] \wurzel{x} [/mm] oder [mm] x^{4} [/mm] nicht.
3. Gesamte Laufzeit: Angenommen, [mm] O(2^{i^{1,2}}) [/mm] wäre eine obere Schranke für die Laufzeit der Berechnung von [mm] 2^{i^{1,2}} [/mm] (ich weiß nicht, ob oder gar warum das so ist). Dann könnte man die gesamte Laufzeit nach oben abschätzen mit: [mm] 2^{n^{1,2}}*\wurzel[1,2]{log_{2}n}. [/mm] Auch hier komme ich nicht weiter, da ich nicht sehe, ob/warum [mm] 2^{n^{1,2}}*\wurzel[1,2]{log_{2}n} [/mm] asymptotisch kleiner als [mm] n^{1,5} [/mm] ist.
|
|
|
| |
|
Des Rätsels Lösung: http://cs.stackexchange.com/questions/21636/why-is-this-function-computable-in-on1-5-time
|
|
|
|
