infostudium.de

von **proxylittle** » 06.10.09 19:29

Ich will diese doofe Gleichung lösen. Hänge aber schon zu lange dran.

T(n) = T(| 3te Wurzel von n |) + 1
T(3) = 1

Ich hab alles versucht... substitution mit dem c-kakk (kann da jedes beliebige O(n hoch irgendwas) herausformen... also irgendwie falch denk ich)

Rekursives einsetzen ergibt:

16^(b) * T( n / 4^(b) ) + b*n^2
b : wie oft ich rekursiv einsetze...

Aber davon werd ich auch nicht schlau, denn wie komm ich dann auch das T(3)=1 ??

Jemand ne idee oder lösung dieser Klausuraufgabe vom 7.Sep.2000 ?

von **Domestos** » 07.10.09 13:58

Also nach dem Schema auf S.37 in den Grundlagen würde ich das so machen:
$T(n)=T(\sqrt[3]{n})+1$

$m=ld(n)$

$T(2^m)=T(2^{\frac{m}{3}})+1$

$S(m)=T(2^m)$

$S(m)=T(\frac{m}{3})+1$

$S(m)=O(log_3m)$

$T(n)=T(2^m)=S(m)=O(log_3m)=O(log_3(ld(n)))$

Aber ich bin mir ehrlich gesagt nicht so sicher, was mit der 1 passiert.

von **proxylittle** » 07.10.09 15:10

uff... hatte wohl nen brett vorm kopf. Ich merk mir das mal mitm logarithmus. Danke schön!

Die 1 kann man weglassen. Erklärung muss ich nochmal suchen, aber bei konstater anzahl an zusätzlichen schritten fällt das immer weg. Is sowas wie:

n^2 + n + 1 ... das ist elemement von O(n^2).

Ich habs mir einfach so trivial gemerkt.

infostudium.de

Forum zum Informatikstudium an der RWTH Aachen

[DSAL] Rekusive gleichung lösen...

Rekusive gleichung lösen...