O-Notation

05.12.2015, 18:26	Adramelec	Auf diesen Beitrag antworten »
O-Notation Hallo, folgende Aufgabe habe ich: Richtig oder falsch? 5nln(n) = O(n) Bei 5n+ln(n) ist es ja so, dass 5n = O(n) + O(ln(n)) und somit ist das ganze O(n) (da das natürlich "stärker" ist) Bei multiplizieren ist es glaube ich so: 5n = O(n) ln(n) = O(ln(n)) = O(n) Somit ist für das ganze O(nn) oder O(n^2) .. Ist das richtig? Danke!
05.12.2015, 22:48	echnaton	Auf diesen Beitrag antworten »
Zeige oder widerlege die Aussage über die Definition des Landau-Symbols. Es stimmt, dass $\begin{eqnarray} 5n \cdot \log(n) \in \mathcal O(n \cdot \log n) \subset \mathcal O(n^2) \end{eqnarray}$ , das bedeutet aber nicht zwangsläufig $\begin{eqnarray} 5n \cdot \log(n) \notin \mathcal O(n) \end{eqnarray}$ .
06.12.2015, 12:48	Adramelec	Auf diesen Beitrag antworten »
Hi! Ok.. Also ist es durchaus richtig, dass ich bei Multiplikation die beiden Landau Ausdrücke multiplizieren muss. Also wenn ich z.B. habe: $\begin{eqnarray} 2^{n} \end{eqnarray}$ und $\begin{eqnarray} 3^{n} \end{eqnarray}$ dann ist ja beides $\begin{eqnarray} \mathcal O(2^{n}) \end{eqnarray}$ und $\begin{eqnarray} \mathcal O(3^{n}) \end{eqnarray}$ Also ist das gemeinsame $\begin{eqnarray} \mathcal O(3^{n}2^{n}) \end{eqnarray}$ oder anders gesagt: $\begin{eqnarray} \mathcal O(6^{n}) \end{eqnarray*}$ richtig? Danke!
06.12.2015, 15:19	echnaton	Auf diesen Beitrag antworten »
Man kann Landau-Symbole miteinander multiplizieren. $\begin{eqnarray} \mathcal O (f(n)) \cdot \mathcal O (g(n)) = \mathcal O(f(n) \cdot g(n)) \end{eqnarray}$ Aber auch das muss erst bewiesen werden.
06.12.2015, 15:31	echnaton	Auf diesen Beitrag antworten »
... wobei die Multiplikation natürlich im richtigen Kontex, zu verstehen ist, so wie du es schon skizziert hast.
06.12.2015, 15:44	Adramelec	Auf diesen Beitrag antworten »
ok, danke
Anzeige

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »