infostudium.de

von **Robert** » 01.08.08 10:55

Hi,

f,g>0 streng monoton wachsend

Zeigen oder wiederlegen Sie: f(n)=O(g(n)) => log_2(f(n))=O(log(g(n)))

Ist unsere Lösung richtig? hab wo gesehen, dass die Aussage stimmen soll, aber ....

Sei f(n)>1 und 0<g(n)<1 für alle n
Dann ex. c>0,n0>0, für alle n>n0: f(n)<=c*g(n)
(dazu muss auch f beschränkt sein, also f,g beschränkt, aber streng monoton wachsend)

d.h. es gilt: f(n)=O(g(n))

Dann ist log_2(f(n))>0
und log_2(g(n)) < 0

Daraus folgt: log_2(f(n))>c*log_2(g(n)) für alle c>0 und unabhängig von der Basis des Logarithmus.

=> Gegenbeispiel zur Behauptung.

Irgendwas falsch vorrausgesetzt oder nicht beachtet? :-/

Grüße

von HE » 01.08.08 11:12

Robert hat geschrieben:Hi,

f,g>0 streng monoton wachsend

Zeigen oder wiederlegen Sie: f(n)=O(g(n)) => log_2(f(n))=O(log(g(n)))

Ist unsere Lösung richtig? hab wo gesehen, dass die Aussage stimmen soll, aber ....

Sei f(n)>1 und 0<g(n)<1 für alle n
Dann ex. c>0,n0>0, für alle n>n0: f(n)<=c*g(n)
(dazu muss auch f beschränkt sein, also f,g beschränkt, aber streng monoton wachsend)

Da wird man sich schon relativ schmerzhaft was konstruieren müssen, damit das funktioniert, aber es dürfte gehen, ja. Im allgemeinen spart man sich sowas, indem man nur $f: \mathbb{N} \rightarrow \mathbb{N}$ betrachtet.

Robert hat geschrieben:d.h. es gilt: f(n)=O(g(n))

Dann ist log_2(f(n))>0
und log_2(g(n)) < 0

Daraus folgt: log_2(f(n))>c*log_2(g(n)) für alle c>0 und unabhängig von der Basis des Logarithmus.

log_x mit x < 1, x > g(n). Was passiert dann?

Marc

von **Robert** » 01.08.08 16:18

HE hat geschrieben:nur $f: \mathbb{N} \rightarrow \mathbb{N}$

Der Drucker hat diese Bedingung leider verschluckt und mit ihr ist mir dann auch klar, warum die Aussage stimmt.

Vielen Dank!

HE hat geschrieben:log_x mit x < 1, x > g(n). Was passiert dann?

Dann hätte man keine streng monoton wachsende Funktion mehr, sondern eine streng monoton fallende.

von **MaoDelinSc** » 01.08.08 17:53

Robert hat geschrieben:
HE hat geschrieben:log_x mit x < 1, x > g(n). Was passiert dann?

Dann hätte man keine streng monoton wachsende Funktion mehr, sondern eine streng monoton fallende.

Warum? HE meint für O(log g(n)) den log zur Basis x und eben ne Bedingung für x... Das hat ja keinerlei Einfluss auf f und g, die bleiben streng monoton wachsend

Sozusagen als Widerlegung deines für alle logarithmen, für den von HE nämlich nicht

von **Stasik** » 01.08.08 18:43

Hi, tut mir leid aber ich verstehe euer problem nicht

als erstes kann man doch erwähnen, dass alle logarithmen unabhängig von der Basis in der gleichen O-Klasse liegen (Basisweschselkonstante).

Danach kann man behaupten, man betrachtet immer nur Zahlen > 1 (als x0), somit sind Logarithmen immer positiv.

Da jetzt g(n) eine obere Schranke für f(n) ist. Und man diese 2 Funktionen in eine stetige, positive und streng monoton wachsende Funktion (log) einsetzt, ist auch log(g(n)) eine Oberschranke für f(n).

In dem Gegenbeispiel verstehe ich einfach nicht woher "dann ist log_2(f(n))>0 und log_2(g(n)) < 0" kommt.... hmm.. steh ich auf dem Schlauch?

von **Merlin Junior** » 01.08.08 21:43

Hey

Die Aufgabe die ihr da gerade diskutiert ist äquivalent zu der Aufgabe 3 aus der Präsensübung 1.
Dort ist kein Definitions- und Wertebereich von f gefordert.

Hat jemand die Musterlösung von der Aufgabe mitgeschrieben?

Wäre toll wenn mir die einer zukommen lassen könnte

mfg
Merlin Junior

von **aRo** » 01.08.08 23:10

hallo!

Ich habe zwar nicht die ganze Diskussion verfolgt, aber Merlin hat recht.
Das ganze per Definition zu zeigen ist nicht sehr schwer, wenn man auf einen Trick kommt, der analog zur Präsenzübung funktioniert.

Abgekürzt haben wir (mit den Voraussetzungen):

$log(f(n)) \leq log(c) + log(g(n))$

Wir definieren uns eine Konstante c' mit
$c' = ( \frac{log(c)}{g(1)} +1 )$

dann gilt $\leq c' \cdot log(g(n))$

für ein neues n0', dass logischerweise max(1,n0) sein muss.

Gruß!

von HE » 02.08.08 11:58

Stasik hat geschrieben:Hi, tut mir leid aber ich verstehe euer problem nicht

als erstes kann man doch erwähnen, dass alle logarithmen unabhängig von der Basis in der gleichen O-Klasse liegen (Basisweschselkonstante).

Danach kann man behaupten, man betrachtet immer nur Zahlen > 1 (als x0), somit sind Logarithmen immer positiv.

Das Problem ist, dass die auf den DSAL-Folien gewählte Definition genau das nicht hergibt. Betrachtet werden allgemein Funktionen $f: \mathbb{N} \rightarrow \mathbb{R}$ . Dazu wird dann noch gefordert, dass c positiv ist, was dann die Sache in den Untergang reißt - das mit der Basiswechselkonstante stimmt schon, aber die ist nicht zwingend positiv.

Marc

von **Stasik** » 02.08.08 12:59

ok, dann.. hmm ist doch doof

von **NeX** » 02.08.08 16:13

aRo hat geschrieben:Abgekürzt haben wir (mit den Voraussetzungen):

$log(f(n)) \leq log(c) + log(g(n))$

Wir definieren uns eine Konstante c' mit
$c' = ( \frac{log(c)}{g(1)} +1 )$

dann gilt $\leq c' \cdot log(g(n))$

für ein neues n0', dass logischerweise max(1,n0) sein muss.

Gruß!

wenn ich das richtig verstehe machst du doch folgende Rechenschritte oder?

$log(f(n)) \leq log(c) + log(g(n)) = \log (g(n)) \cdot ( \frac{\log (c)}{\log (g(n))} + 1)$

oder?

Wie kommst du also darauf

$c' = ( \frac{log(c)}{g(1)} +1 )$

das so wählen zu dürfen ...also $\log (g(n))$ durch $g(1)$ zu ersetzen?

oder habe ich etwas nicht beachtet ?

von **aRo** » 02.08.08 18:35

naja..
mir fällt grad auf, ich hätte wohl lieber log(g(1)) nehmen sollen

Sorry!
also unser Ziel ist doch
$log(f(n)) \leq c' \cdot log(g(n))$ zu folgern, weil wir dann sagen können, dass $log(f(n)) = O(log(g(n))$ ist.

Wir müssen also so eine Konstante c' finden. Die korrigierte Konstante erfüllt die Bedingung, denn es gilt:
$log(f(n)) \stackrel{Vor.}{\leq} log(c) + log(g(n)) \stackrel{s.u.}{\leq} c' log(g(n))$

2.Ungleichung gilt, weil:
$c' \cdot log(g(n)) = \frac{log(c)}{log(g(1))} \cdot log(g(n)) + log(g(n))$

Wir fragen uns also, ob log(c)/log(g(1)) * log(g(n)) >= log(c) ist.
Das ist offensichtlich richtig, wenn log(g(n)) >= log(g(1)).
Das ist richtig für n>=1, denn g ist monoton steigend und der logarithmus ebenfalls..

Wir wählen also unser neues n0' wie folgt:
n0' = max(1,n0). Denn größer gleich 1 muss es wie eben erwähnt sein, und größer gleich n0 auch, denn sonst gilt unsere erste Ungleichung gar nicht erst.

Naja, ist ein bisschen verwirrend geraten, hoffe du verstehst es dennoch

von **NeX** » 03.08.08 14:32

aRo hat geschrieben:2.Ungleichung gilt, weil:
$c' \cdot log(g(n)) = \frac{log(c)}{log(g(1))} \cdot log(g(n)) + log(g(n))$

Wir fragen uns also, ob $log(c)/log(g(1)) * log(g(n)) \geq log(c)$ ist.
Das ist offensichtlich richtig, wenn $log(g(n)) \geq log(g(1)).$
Das ist richtig für n>=1, denn g ist monoton steigend und der logarithmus ebenfalls..
.....

Aber schätzen wir denn nicht in diesem Moment hier

$log(c)/log(g(1)) * log(g(n)) \geq log(c)$ die Gleichung nach oben ab

da wir $\log g(n)$ nach $\log g(1)$ abschätzen....und somit die Gleichung größer machen....

Klick......wir dürfen das ganze ja größer machen sofern es für ein $c'$ gilt......

das ist mein fehler gewesen ....hoffe ich

Danke für deine Geduld

von **YtKM** » 04.08.08 15:52

Ist denn dabei gewährleistet, dass c'>0 ist?

Du sagst, dass du einfach dein n=max(1,n_0) wählst. Allerdings sagt das n doch nichts über den Funktionswert von g selbst aus. Zumindest nichts über seine absolute Größe.

Könnte nicht g streng monoton wachsend und im Grenzwert gegen unendlich gegen 1 gehen?
Dann können wir unser c' nicht so einfach umdefinieren, oder?

Viele Grüße

infostudium.de

Forum zum Informatikstudium an der RWTH Aachen

[DSAL] f=O(g) => log_2(f)=O(log g)

f=O(g) => log_2(f)=O(log g)

Re: f=O(g) => log_2(f)=O(log g)

Re: f=O(g) => log_2(f)=O(log g)

Re: f=O(g) => log_2(f)=O(log g)