Informatiker Board | Theoretische Informatik

Informatiker Board » Themengebiete » Theoretische Informatik » Beweis zur Komplexität

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

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

Beweis zur Komplexität

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

aRo
Jungspund

Dabei seit: 25.10.2007
Beiträge: 18

Beweis zur Komplexität

Zitatantwort auf diesen Beitrag erstellen

Hallo!

Folgendes ist zu zeigen oder widerlegen:

$[latex] f \in \Theta(g) \wedge \lim_{n \to \infty} {\frac{h(n)}{g(n)}}=0 \Rightarrow f+h \in \Theta(g)[/latex]$

Also die gegebenen Voraussetzungen dürften sich ja wie folgt übersetzen lassen:

$[latex]\exists c>0 \exists n_0>0 \forall n \geq n_o : g(n)/c \leq f(n) \leq cg(n)[/latex]$

$[latex]\exists c'>0 \exists n_0'>0 \forall n \geq n_o' : h(n) \leq g(n) \cdot c'[/latex]$

Daraus folgt:

$[latex] h(n)+g(n)/c \leq f(n)+h(n) \leq g(n)c+g(n)c' [/latex]$

Wenn ich jetzt abschätze, dann käme ich doch auf:

$[latex] g(n)c' + g(n)/c \leq f(n)+h(n) \leq g(n) \cdot (c+c') [/latex]$

Dann müsste doch gelten:

$[latex] c' + \frac{1}{c} = \frac{1}{c+c'} [/latex]$

Was ich zu einer Beziehung zwischen c und c' auflösen kann, und sehen kann, dass c' >= 2 sein muss.
Wenn das dann gilt, dürfte die Aussage stimmen, oder?

Hoffe auf Antwort!
aRo

20.05.2008 13:17

Nehmen Sie aRo in Ihre Freundesliste auf

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

Hallo,

ich habs nur kurz mal überflogen:
Du darfst sogar annehmen, dass |h(n)| echt kleiner als c'*|g(n)| ist, denn h ist in o(g) und nicht bloß in O(g)

Bei dem gesamten Beweis hast du eine nicht unerhebnliche Schwierigkeit komplett ignoriert: Die Beträge. Für die obere Schranke sind die Beträge egal, da

|f(n) + h(n)| <= |f(n)| + |h(n)| (Dreiecksungleichung).

Leider ist dies für die untere Schranke so nicht mehr anwendbar.

20.05.2008 15:01

Nehmen Sie Tobias in Ihre Freundesliste auf

aRo
Jungspund

Dabei seit: 25.10.2007
Beiträge: 18

Zitat:

Original von Tobias

Du darfst sogar annehmen, dass |h(n)| echt kleiner als c'*|g(n)| ist, denn h ist in o(g) und nicht bloß in O(g)

okay, stimmt, aber ich dachte das mir die Erkenntnis keinen Vorteil bringt.

Zu den Beträgen:

Ich bin gerade leider etwas verwirrt. Wieso ist es mir bei der oberen Schranke egal? Sollte ich hier nicht nach oben abschätzen statt nach unten um "auf der sicheren Seite" zu sein?

Ich weiß, dass ich da schonmal Schwierigkeiten hatte sowas nachzuvollziehen..

Und wie kriege ich nun die jeweils andere Seite in den Griff?

Außerdem:
Mit den Beträgen hast du natürlich recht. Die tauchen bei unserer Definition nicht auf, aber da wurden die Funktionen f und g auch positiv definiert. Da nun davon nichts in der Aufgabe steht, muss ich das wohl jetzt berücksichtigen.

20.05.2008 17:48

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

Ok, wenn du die Beträge nicht brauchst, ist es garnicht so schwer. Ich benutze $[latex]f+h \in \Theta(g) \iff f+h \in \mathcal{O}(g) \wedge g \in \mathcal{O}(f+h)[/latex]$

Die obere Schranke hattest du ja schon gezeigt:
$[latex]f(n) + h(n) \leq c \cdot g(n) + c' \cdot g(n) = (c + c') g(n)[/latex]$ für alle $[latex]n \geq \max\{n_0, n_0'\} \quad \Rightarrow f+h \in \mathcal{O}(g)[/latex]$

Die untere Schranke ist auch ganz einfach:
$[latex]g(n) \leq c \cdot f(n) \leq c \cdot f(n) + h(n) \leq \max\{c, 1\} \cdot (f(n) + h(n))[/latex]$ für alle $[latex]n \geq n_0 \quad \Rightarrow g \in \mathcal{O}(f+h)[/latex]$

Man kann nun auch hingehen, und die direkte Definition von $[latex]\Theta(g)[/latex]$ verwenden:

$[latex]\frac{1}{\xi} \cdot g(n) \leq f(n) + h(n) \leq \xi \cdot g(n)[/latex]$ für alle $[latex]n \geq \max\{n_0, n_0'\}[/latex]$ und $[latex]\xi := \max\{1, c+c'\}[/latex]$

20.05.2008 20:14

aRo
Jungspund

Dabei seit: 25.10.2007
Beiträge: 18

hi!

ja, vielleicht sollten wir die Beträge weglassen.

Obere Schranke verstehe ich, hatte ich ja auch so.

Zur unteren Schranke:

Wieso soll denn $[latex] c \cdot f(n) \leq c \cdot f(n) + h(n) [/latex]$ gelten?!

Ich behaupte das ist falsch, weil wir ja nun h(n)>0 annehmen (vgl. beträge)...

20.05.2008 20:28

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

Zitat:

Ich behaupte das ist falsch, weil wir ja nun h(n)>0 annehmen (vgl. beträge)...

Gerade unter dieser Annahme ist es doch richtig? Addiere ich etwas positives auf c*f(n) drauf, so wird das Ergebnis größer!?

20.05.2008 20:44

aRo
Jungspund

Dabei seit: 25.10.2007
Beiträge: 18

na, was habe ich mir denn da gedacht...entschuldige.

okay, ich habs verstanden Augenzwinkern

20.05.2008 20:46

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Beweis zur Komplexität