Informatiker Board | Theoretische Informatik | rekurrenzgleichung beweisen

Informatiker Board » Themengebiete » Theoretische Informatik » rekurrenzgleichung beweisen » Antwort erstellen

» Hallo Gast [Anmelden|Registrieren]

Antwort erstellen

Benutzername:

(du bist nicht eingeloggt!)

Thema:

Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

Smilies: 21 von 33

einfacher Modus erweiterter Modus

aktuellen Tag schließen

alle Tags schließen

Spamschutz:
Text aus Bild eingeben

URLs automatisch umwandeln: fügt automatisch [url] und [/url] in Internet-Adressen ein.
Smilies in diesem Beitrag deaktivieren.
BBCode in diesem Beitrag deaktivieren.
Bilder in diesem Beitrag deaktivieren.
Signatur anzeigen: Soll die im Profil eingestellte Signatur an den Beitrag angehangen werden?
Nachrichtenlänge überprüfen

Die letzten 8 Beiträge

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

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

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

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

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.

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?

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

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