rekurrenzgleichung beweisen

28.04.2008, 22:43

xole_X

rekurrenzgleichung beweisen

Ich soll zeigen, dass
T(n) = T(0.5n + 10) + n in O(n*lg(n)) liegt...

wie mach ich das am besten?

ich habs folgender maßen probiert:

T(n)<=c* (0.5n+10)*lg(0.5n+10)+n

jetzt nehm ich als abschätzung 0.5n+10<=n gilt für alle n>= 20

<= c*(0.5n+10)*lg(n)+n<=c*n*lg(n) ----> aber ab welchem n gilt das hier bei c=1 zB...ab ca 300 hab am graph abgelesen, aber wie gesagt, abgelesen und nicht errechnet...naja das waren jetzt so meine erfolglosen versuche...hoffe mir kann jemand helfen

29.04.2008, 14:16

Auf diesen Beitrag antworten »

Tobias

Kennst du das Master-Theorem? Damit beweist man, dass sogar $[latex]T(n) \in \Theta(n)[/latex]$ und damit natürlich auch $[latex]T(n) \in \mathcal{O}(n\log n)[/latex]$

Ein alternativer Beweis ist dieser:

Für $[latex]n \to \infty[/latex]$ fällt die Konstante 10 nicht mehr ins Gewicht. Man kann also sogleich sagen, dass $[latex]T(\frac{n}{2} + 10) + n \in \mathcal{O}(f) \Rightarrow T(\frac{n}{2}) + n \in \mathcal{O}(f)[/latex]$ für ein geeignetes f.

Wir lösen nun sukkzessive auf:

$[latex]T(n) = T(\frac{n}{2}) + n = T(\frac{n}{4}) + \frac{n}{2} + n = \ldots = T(1) + \sum_{i=0}^{\lfloor \log n \rfloor}\frac{n}{2^{i}}[/latex]$

Mit der geometrischen Reihe schätzen wir die Summe gegen 2 ab:
$[latex]T(n) = T(1) + \sum_{i=0}^{\lfloor \log n \rfloor}\frac{n}{2^{i}} \leq T(1) + n \cdot \sum_{i=0}^{\infty}\left(\frac{1}{2}\right)^i = T(1) + 2n[/latex]$

Nun gehe ich davon aus, dass maximal $[latex]T(1) \in \mathcal{O}(n)[/latex]$ . Hier fehlen deine Angaben, deshalb nur eine Vermutung.

Damit: $[latex]T(n) \in \Theta(n)[/latex]$

Dein Beweis benutzt Induktion über die Rekursionstiefe und ist auch gangbar, denke ich. Hier musst du dich aber etwas deutlicher an dem Vergehen der Induktion orientieren. Es fehlt z.B. der Induktionsanfang. Es ist dann nicht wichtig, ab welchem $[latex]n \geq n_0[/latex]$ dein Beweis gilt, sondern nur dass es irgendwann gilt. Dafür kannst du z.B. das +n am Ende auch durch $[latex]n \leq n\cdot \log n[/latex]$ abschätzen, dann ausklammern und die Konstante erhöhen:

$[latex]T(n) \leq \ldots \leq c \cdot n \lg(n) + n \leq c \cdot n \lg(n) + n \lg(n) = (c+1) n \cdot\lg(n) = c' \cdot n \cdot \lg(n)[/latex]$

29.04.2008, 15:28

Auf diesen Beitrag antworten »

xole_X

ja kenn das mastertheorem, aber was mach ich denn mit der 10 in T(n) = T(0.5n + 10)

Das Mastertheorem ist doch nur für Gleichungen der Form:

T(n) = a*T(n/b)+f(n)

a ist bei meiner gleichung : a=1 aber was ist b?

29.04.2008, 15:48

Auf diesen Beitrag antworten »

Tobias

b ist 2 wegen

Zitat:

Für $[latex]n \to \infty[/latex]$ fällt die Konstante 10 nicht mehr ins Gewicht. Man kann also sogleich sagen, dass $[latex]T(\frac{n}{2} + 10) + n \in \mathcal{O}(f) \Rightarrow T(\frac{n}{2}) + n \in \mathcal{O}(f)[/latex]$ für ein geeignetes f.

29.04.2008, 16:32

Auf diesen Beitrag antworten »

xole_X

Zitat:

Original von Tobias

Dein Beweis benutzt Induktion über die Rekursionstiefe und ist auch gangbar, denke ich. Hier musst du dich aber etwas deutlicher an dem Vergehen der Induktion orientieren. Es fehlt z.B. der Induktionsanfang. Es ist dann nicht wichtig, ab welchem $[latex]n \geq n_0[/latex]$ dein Beweis gilt, sondern nur dass es irgendwann gilt. Dafür kannst du z.B. das +n am Ende auch durch $[latex]n \leq n\cdot \log n[/latex]$ abschätzen, dann ausklammern und die Konstante erhöhen:

$[latex]T(n) \leq \ldots \leq c \cdot n \lg(n) + n \leq c \cdot n \lg(n) + n \lg(n) = (c+1) n \cdot\lg(n) = c' \cdot n \cdot \lg(n)[/latex]$

wenn ich ehrlich bin, ich blick da noch net so 100% durch.
wie leite ich denn jetzt mein induktionsanfang her aus deiner abschätzung?
http://de.wikipedia.org/wiki/Substitutionsmethode
hab mich bisschen hierran orientiert, weil wir bisher nur mastertheorem und substitutionsmethode hatten. das mastertheorem aber nur so als absicherung und nicht als alleiniger beweis.
bis punkt4 beispiel1 in wikipedia bin ich mittlerweile gekommen, aber ich verstehe 5. Induktion nicht so ganz.wie kommen sie da auf den induktionsanfang n=2 und wieso ist da T(2) = 2 unglücklich

auch das mastertheorem scheint nicht so gut zu funktionieren:
damit n*log(n) gilt muss f(n)€ O(n^(lg1))
f(n) ist jedoch n, aber n ist nicht element von O(n^(lg1))

29.04.2008, 18:02

Auf diesen Beitrag antworten »

Tobias

Deshalb schrieb ich ja schon, dass das Mastertheorem beweist, dass $[latex]T(n) \in \Theta(n)[/latex]$

Das ist übrigens der dritte Fall hier: http://de.wikipedia.org/wiki/Master-Theorem

29.04.2008, 18:10

Auf diesen Beitrag antworten »

xole_X

[quote]Original von Tobias
Deshalb schrieb ich ja schon, dass das Mastertheorem beweist, dass $[latex]T(n) \in \Theta(n)[/latex]$
[quote]

kann ich sagen, die aussage stimmt, da $[latex]T(n) \in \Theta(n) <= O(n*lg(n))[/latex]$

29.04.2008, 18:49

Auf diesen Beitrag antworten »

Tobias

Es ist wieder einmal Zeit, sich selbst zu zitieren:

Zitat:

Kennst du das Master-Theorem? Damit beweist man, dass sogar $[latex]T(n) \in \Theta(n)[/latex]$ und damit natürlich auch $[latex]T(n) \in \mathcal{O}(n\log n)[/latex]$

Zitat:

kann ich sagen, die aussage stimmt, da $[latex]T(n) \in \Theta(n) <= O(n*lg(n))[/latex]$

Ja, das kann man sagen. Die Schreibweise $[latex]\Theta(n) \leq O(n \lg(n))[/latex]$ ist ein wenig unorthodox aber ich denke man weiß, was du sagen willst. Strenger formuliert müsste es so lauten:

$[latex]\big( f \in \Theta(n) \Rightarrow f \in \mathcal{O}(n \log n) \big) \iff \Theta(n) \subseteq \mathcal{O}(n \log n)[/latex]$

Neue Frage »

Antworten »

rekurrenzgleichung beweisen

Verwandte Themen