Informatiker Board | Druckvorschau: rekurrenzgleichung beweisen

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
-- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
--- rekurrenzgleichung beweisen (http://www.informatikerboard.de/board/thread.php?threadid=411)

Geschrieben von xole_X am 28.04.2008 um 22:43:

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

Geschrieben von Tobias am 29.04.2008 um 14:16:

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]$

Geschrieben von xole_X am 29.04.2008 um 15:28:

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?

Geschrieben von Tobias am 29.04.2008 um 15:48:

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.

Geschrieben von xole_X am 29.04.2008 um 16:32:

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))

Geschrieben von Tobias am 29.04.2008 um 18:02:

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

Geschrieben von xole_X am 29.04.2008 um 18:10:

[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]$

Geschrieben von Tobias am 29.04.2008 um 18:49:

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]$