0 Daumen
299 Aufrufe


ich habe eine kurze Frage und zwar liegt \(n\cdot \log(n)\) wirklich in \(\Theta(n^3)\)?
Und wenn ja, warum?

Und was ist wenn wir \(n\cdot \log(n^4)\) haben? In welcher Theta-Notation liegt diese dann?

Avatar von

1 Antwort

0 Daumen
 
Beste Antwort

Hallo :-)

Ich glaube du meinst \(n\cdot \log(n)\in \Theta(n^3)\). Um das zu zeigen, musst du zeigen:

1.) \(n\cdot \log(n)\in \Omega(n^3)\) und

2.) \(n\cdot \log(n)\in \mathcal{O}(n^3)\)

Aussage 1.) ist aber falsch und Aussage 2.) ist richtig, sodass nur \(n\cdot \log(n)\in \mathcal{O}(n^3)\) gilt und \(n\cdot \log(n)\notin \Omega(n^3)\), sodass auch \(n\cdot \log(n)\notin \mathcal{O}(n^3)\cap \Omega(n^3) = \Theta(n^3)\).


Für \(n\cdot \log(n^4)=4\cdot n\cdot \log(n)\) zählt genau dasselbe, wie oben.

Avatar von 14 k

Oh, jetzt ist mir einiges klar. Ich Danke Dir für die ausführliche und schöne Erklärung! :-D

Eine Frage habe ich noch:
Wie zeigt man sowas eigentlich bzw. rechnet denn da? Mit Master-Theorem?

Zum Beispiel habe ich diese Aufgabe hier gegeben, aber ich weiß leider nicht wie man das hier genau beweisen kann:

blob.png

Da musst du auch nur wieder die Definitionen nachprüfen:

Es sei \(g: \mathbb{N}\rightarrow \mathbb{R}\).

$$1.)\quad \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) \text{ und } f(n)\leq \alpha\cdot g(n) }  \} $$

$$2.)\quad \Omega(g):=\{f:\ \mathbb{N}\rightarrow \mathbb{R}:\ \exists \beta>0 \ \exists n_1 \in \mathbb{N} \ \forall n\geq n_1:\ \underbrace{0\leq \beta \cdot g(n) \leq f(n)}_{0\leq \beta\cdot g(n) \text{ und } \beta\cdot g(n)\leq f(n) }  \} $$

$$3.)\quad \Theta(g):=\mathcal{O}(g)\cap \Omega(g)$$


Zu 1.). Finde also ein \(\alpha>0\) und eine Stelle \(n_0\in\mathbb{N}\), sodass für alle \(n\geq n_0\) die Ungleichung \(0\leq n\cdot \log_3(n^2)\leq \alpha\cdot n\cdot (\log_3(n))^2\) gilt. Diese Parameter kann man beim bloßen Versuch der Abschätzung einsehen:

\(0\stackrel{n\geq 1}{\leq} \log_3(n)\)

Daraus folgt

$$0\stackrel{n\geq 1}{\leq} n\cdot \log_3(n^2)=2\cdot n\cdot \underbrace{\log_3(n)}_{\geq 1,\space \forall n\geq 3}\stackrel{n\geq 3}{\leq }2\cdot n\cdot \log_3(n)\cdot \log_3(n)=2\cdot n\cdot (\log_3(n))^2$$

Also gilt mit \(\alpha=2\) und \(n_0=3\) für alle \(n\geq 3\) die Abschätzung

\(0\leq n\cdot \log_3(n^2)\leq \alpha\cdot n\cdot (\log_3(n))^2\),

sodass \(n\cdot \log_3(n^2)\in \mathcal{O}(n\cdot (\log_3(n))^2)\) gilt.


Zu 2.). Diese Aussage ist falsch. Um das zu zeigen, muss man also die Aussage

\(n\cdot \log_3(n^2)\notin \Omega(n\cdot (\log_3(n))^2)\) betrachten. In Quantorenschreibweise sieht das so aus:

$$  \forall \beta>0 \ \forall n_1 \in \mathbb{N} \ \exists n\geq n_1:\ \underbrace{0> \beta\cdot n\cdot (\log_3(n))^2}_{(1)} \text{  oder } \underbrace{\beta\cdot n\cdot (\log_3(n))^2> n\cdot \log_3(n^2)}_{(2)}  $$

(1) ist offensichtlich immer falsch.

Also muss man (2) zeigen, sodass diese Oder-Aussage wahr ist. Finde also in Abhängigkeit von \(\beta>0\) und \(n_0\in \mathbb{N}\) ein \(n\geq n_0\), sodass Abschätzung (2) gilt.

Dafür probiert man etwas rum:

\(\beta\cdot n\cdot (\log_3(n))^2> n\cdot \log_3(n^2)\).

Zu kompliziert. Ich betrachte stattdessen:

\(\beta\cdot (\log_3(n))^2> \log_3(n^2)=2\cdot \log_3(n)\).

Immernoch zu kompliziert. Also:

\(\beta\cdot \log_3(n)> 2\)  bzw. \(\log_3(n)>\frac{2}{\beta}\)   bzw.  \(n>3^{\frac{2}{\beta}}\)

Das letzte sieht sehr vielversprechend aus. Um jetzt noch \(\beta>0\) und \(n_0\in \mathbb{N}\) ins Boot zu holen, wähle ich mein finales \(n\in \mathbb{N}\) folgendermaßen:

\(n>\max\left(\beta, n_0,3^{\frac{2}{\beta}}\right)\). Dann ist \(n>n_0\) und \(n>3^{\frac{2}{\beta}}\). Also hat man:

$$\begin{aligned}n&>3^{\frac{2}{\beta}}>1\\[10pt]&\Leftrightarrow \log_3(n)>\frac{2}{\beta}\\[10pt]&\Leftrightarrow \beta\cdot \log_3(n)>2\\[10pt]&\Leftrightarrow \beta\cdot (\log_3(n))^2>2\cdot \log_3(n)\\[10pt]&\Leftrightarrow \beta\cdot n\cdot (\log_3(n))^2>2\cdot n\cdot \log_3(n)=n\cdot \log_3(n^2)\end{aligned}.$$

Also hat man damit \(n\cdot \log_3(n^2)\notin \Omega(n\cdot (\log_3(n))^2)\) gezeigt.

Insgesamt gilt also \(n\cdot \log_3(n^2)\notin \Theta(n\cdot (\log_3(n))^2)\).

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community