Informatiker Board | Theoretische Informatik | rekurrenzgleichung beweisen

Informatiker Board » Themengebiete » Theoretische Informatik » rekurrenzgleichung beweisen

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

rekurrenzgleichung beweisen

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

xole_X
Grünschnabel

Dabei seit: 23.10.2007
Beiträge: 9

rekurrenzgleichung beweisen

Zitatantwort auf diesen Beitrag erstellen

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

28.04.2008 22:43

Nehmen Sie xole_X in Ihre Freundesliste auf

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

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

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Tobias: 29.04.2008 14:16.

29.04.2008 14:16

Nehmen Sie Tobias in Ihre Freundesliste auf

xole_X
Grünschnabel

Dabei seit: 23.10.2007
Beiträge: 9

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:28

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

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 15:48

xole_X
Grünschnabel

Dabei seit: 23.10.2007
Beiträge: 9

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

Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von xole_X: 29.04.2008 16:54.

29.04.2008 16:32

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

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:02

xole_X
Grünschnabel

Dabei seit: 23.10.2007
Beiträge: 9

[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:10

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

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

29.04.2008 18:49

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » rekurrenzgleichung beweisen