0 Daumen
1,5k Aufrufe

Aufgabe:

Beweisen Sie die folgenden Ungleichungen. Zu einem korrekten Beweis gehört die Angabe einer Konstante c > 0 und eines N ∈ ℕ, sodass für alle n ≥ N gilt: f(n) ≤ c · g(n).

Hinweis: Benutzen Sie die Definition der O-Notation und vollständige Induktion.

a) O(2n) < O(n!)

b) O(log(n)) < O(n \sqrt{n} )

c) O(n · log(n)) < O(n2)


Problem/Ansatz:

Wie findet man die passende Konstante? Wurde halt so gar nicht erklärt wie man drauf kommen soll und voll. Induktion sollte dann ansich funktionieren. Wäre nett, wenn es bei a) oder (vorallem) b) gezeigt werden könnte.

Avatar von

Wie kommst gerade auf 1? Weil in einem Beispiel wie in c) hat der Übungsleiter logab bestimmt, deshalb bin ich verwirrt, wie man das konkret bestimment soll.

1 Antwort

0 Daumen

Als passende Konstante kannst du 1 verwenden.

Das N bekommst du indem du dir die Graphen von einem Computer zeichnen lässt.

Jetzt fehlt nur noch die Induktion.

Avatar von 107 k 🚀

Wie kommst du gerade auf 1? Denn in dem einzigen Beispiel, dass gezeigt wurde (fast identisch mit c), nur das nicht O(n2), nur O(n) verwendet wurde. Da wurde dann aufwendig für die Konstante loga(b) gewählt.

c), nur das nicht O(n2), nur O(n) verwendet wurde.

Dass kann nicht sein. Die Behauptung

        O(n·log n) ≤ O(n)

ist falsch.

Da wurde dann aufwendig für die Konstante loga(b) gewählt.

Bist du sicher, dass das c war und nicht N?

Wie kommst gerade auf 1

Ich habe mir die Graphen der Funktionen angeschaut.

O(2n) < O(n!)

Links wird beim Übergang von n zu n+1 mit 2 multipliziert.

Rechts wird beim Übergang von n zu n+1 mit n+1 multipliziert.

Es ist intuitiv klar, das es rechts schneller wächst, da ändert auch ein konstanter Faktor c nichts dran. Also nehme ich den einfachsten legalen Faktor.

O(log(n)) < O(n \sqrt{n} )

Die Exponentialfunktion wächst schneller als jede Potenzfunktion.

Umgekährt wächst dann natürlich die Umkehrfunktion der Exponentialfunktion langsamer als die Umkehrfunktion jeder Potenzfunktion.

Ein Beispiel wo c = 1 nicht reicht, ist

O(n + sin(n)) ≤ O(n),

aber so abstrus sehen deine Aufgaben ja nicht aus.

Ich hab jetzt nochmal genauer geschaut, was der Leiter gemacht hat:

Sein Beispiel ist: O(log n) ≤ O(n)

logab ≡ const.

Basis des Log. ist unerheblich.

Dann wählt er O(log2n) ≤ O(n)

Und dann macht er ganz normal Induktion.

Aber die Schritte da oben sind irgendwie komisch, weil er nicht erklärt, wie er das gewählt hat. Er hat einfach log umgeschrieben fertig.

logxb = logax/(logab)

In der Ungleichung

        logann\log_a n \leq n

hängt das NN, ab dem die Ungleichung für alle nNn \geq N erfüllt ist, von aa ab. Hat man aber für jedes aa so ein NN gefunden, dann ist O(logan)O(n)O(\log_a n) \leq O(n) bewiesen. Und zwar wohlgemerkt mit Wahl von c=1c = 1.

Es könnte sich als schwierig erweisen, für jedes aa ein geeignetes NN zu finden. Deshalb sucht man zunächst nur ein NN für den Fall a=2a=2. Hier ist N=0N=0 eine geeignete Wahl. Man zeigt also zunächst nur die Ungleichung

        log2nn\log_2 n \leq n

für alle n0n\geq 0. Und zwar auch hier wohlgemerkt mit Wahl von c=1c=1. Das ist vermutlich der Teil wo ihr vollständige Induktion angewendet habt.

Mit Basiswechel (siehe Satz unten) kann man dann argumentieren: Für alle n0n \geq 0 gilt

        log2nn : log2a    log2nlog2a1log2anBasiswechsel    logan1log2an\begin{aligned} & & \log_{2}n & \leq n & & |:\log_{2}a\\ & \implies & \frac{\log_{2}n}{\log_{2}a} & \leq\frac{1}{\log_{2}a}\cdot n & & \text{Basiswechsel}\\ & \implies & \log_{a}n & \leq\frac{1}{\log_{2}a}\cdot n\end{aligned}

Damit ist O(logan)O(n)O(\log_a n) \leq O(n) bewiesen mit Wahl von c=1log2ac = \frac{1}{\log_2 a} und N=0N = 0.

Satz (Basiswechsel). Seien p,q>0p,q>0 mit p1p\neq1 und q1q\neq1 und r>0r>0. Dann ist

        logpr=logqrlogqp\begin{aligned} \log_{p}r & =\frac{\log_{q}r}{\log_{q}p} \end{aligned}

Beweis. Sei xRx\in\mathbb{R} mit px=rp^{x}=r. Dann gilt einerseits

        px=rlogplogp(px)=logprDef. Logarithmusx=logpr\begin{aligned} p^{x} & =r & & |\log_{p}\\\log_{p}\left(p^{x}\right) & =\log_{p}r & & \text{Def. Logarithmus}\\ x & =\log_{p}r \end{aligned}

und andererseits

        px=rlogqlogq(px)=logqr3. Logarithmusgesetzxlogqp=logqr : logqpx=logqrlogqp\begin{aligned} p^{x} & =r & & |\log_{q}\\ \log_{q}\left(p^{x}\right) & =\log_{q}r & & \text{3. Logarithmusgesetz}\\ x\log_{q}p & =\log_{q}r & & |:\log_{q}p\\ x & =\frac{\log_{q}r}{\log_{q}p} \end{aligned}.

Also ist auch

        logpr=logqrlogqp\log_{p}r=\frac{\log_{q}r}{\log_{q}p}\qquad\qquad\qquad\qquad\qquad\qquad\square

Dieser Satz besagt, dass sich die Funktionen

        xlogpxx\mapsto \log_p x

und

        xlogqxx\mapsto \log_q x

nur um den konstanten Faktor 1logqp\frac{1}{\log_q p} unterscheiden.

logxb = logax/logab

Das stimmt so nicht. Schau noch mal in den Satz zum Basiswechsel rein.

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen