0 Daumen
691 Aufrufe

Aufgabe:

T1(n) = 2^n + 7

T2(n) = 2n³ + 7n + 5

T3(n) = 14n² + 300

a) Geben Sie (ohne Beweis) obere Grenzen für die Laufzeiten von und T3 an, die möglichst dicht an der tatsächlichen Laufzeit liegen sollen.

b) Beweisen Sie, dass T2 in der von ihnen genannten Laufzeitklasse liegt.

c) Beweisen Sie, dass T2 nicht in O(n²) liegt.

Ansätze:

a) T1: O(2^n)

T2: O(n³)

T3: O(n²)

Allerdings weiß ich nicht wie ich das in b) und c) beweisen soll? 

Avatar von

1 Antwort

0 Daumen

Hallo :-)

Auch wenn diese Frage schon länger zurückliegt, gehe ich mal drauf ein: a) ist richtig gelöst.


Die formale Definition für die Groß O-Notation lautet in etwa:
Es sei \(g: \mathbb{N}\rightarrow \mathbb{R}\). Dann ist$$ \mathcal{O}(g):=\{f:\ \mathbb{N}\rightarrow \mathbb{R}:\ \exists \alpha>0 \ \exists n_0 \in \mathbb{N} \ \forall n\geq n_0:\ \underbrace{0\leq f(n) \leq \alpha \cdot g(n)}_{0\leq f(n) \ \land f(n)\leq \alpha\cdot g(n) }  \} $$

Zu b)

\(0\stackrel{n\geq 0}{\leq}T_2(n)=2n^3+7n+5\stackrel{n\geq 1}{\leq} 2n^3+7n^3+5\stackrel{n\geq 2}{\leq}{2n^3+7n^3+n^3}=\underbrace{10}_{=\alpha} n^3\). Es gibt also ein \(\alpha=10\) und ein \(n_0=2\), sodass für alle \(n\geq n_0=2\) die Abschätzung \(0\leq T_2(n)\leq \alpha \cdot n^3\) gilt. Also gilt per Definition \(T_2\in \mathcal{O}(n^3)\).


Zu c). Hier soll gezeigt werden, dass \(T_2\notin \mathcal{O}(n^2)\), also nicht \(T_2\in \mathcal{O}(n^2)\) gilt. Man soll also die Kontraposition der Groß O-Notation nachweisen:

$$ f \notin \mathcal{O}(g) \quad \Leftrightarrow \quad \forall \alpha>0 \ \forall n_0 \in \mathbb{N} \ \exists n\geq n_0:\ 0> f(n) \lor f(n) > \alpha \cdot g(n)  $$

Wir müssen also in Anhängigkeit von \(\alpha>0\) und \(n_0\in \mathbb{N}\) ein \(n\geq n_0\) finden. sodass \(0> T_2(n)\) oder \( T_2(n) > \alpha \cdot n^2\) gilt.

Da \(T_2\) für alle \(n\in \mathbb{N}\) nichtnegativ ist, ist \(0>T_2\) immer falsch.

Also muss man \( T_2(n) > \alpha \cdot n^2\) beweisen, damit diese Oder-Aussage wahr wird.

Wähle \(n>\max\left(n_0,\frac{\alpha}{2}\right)>0\). Dann ist

\(\begin{aligned} &n>\frac{\alpha}{2}\\[10pt]&\Leftrightarrow 2n>\alpha\\[10pt]&\Leftrightarrow 2n-\alpha>0\\[10pt]&\Leftrightarrow n\cdot (2n-\alpha)>0\\[10pt]&\Leftrightarrow n\cdot (2n-\alpha)+7>7\\[10pt]&\Leftrightarrow n\cdot (n\cdot (2n-\alpha)+7)>7\cdot n\\[10pt]&\Leftrightarrow n\cdot (n\cdot (2n-\alpha)+7)+5>7\cdot n+5>0\\[10pt]&\Rightarrow \underbrace{n\cdot (n\cdot (2n-\alpha)+7)+5}_{2n^3-\alpha\cdot n^2+7n+5}>0\\[10pt]&\Leftrightarrow T_2(n)=2n^3+7n+5>\alpha\cdot n^2 \end{aligned}\)

Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community