Zusammenhänge bei Landau-Notation

17.03.2023, 11:46	Malcang	Auf diesen Beitrag antworten »
Zusammenhänge bei Landau-Notation Hallo liebe Leute, ich tue mir immerwieder sehr schwer mit der Landau-Notation. Betrachte ich mal die Komplexitätsklassen $\begin{eqnarray} P=\bigcup\limits_{k\in\mathbb N}DTIME(n^k) \end{eqnarray}$ und $\begin{eqnarray} DTIME(2^{\mathcal{O}(\log(n)}) \end{eqnarray}$ (log meint den Logarithmus zur Basis 2). Nach unserem Skript sind diese gleich und ich sehe das auch ein, mir fällt nur das formale hier sehr schwer. Es ist doch $\begin{eqnarray} f=\mathcal{O}(\log(n)) \Leftrightarrow \exists c\in\mathbb N: f(n) = c\cdot\log(n) \end{eqnarray}$ . Also ist $\begin{eqnarray} 2^{\mathcal{O}(\log(n)} = 2^{c\log(n)} = n^c \forall c\in\mathbb N \end{eqnarray}$ . Damit kann ich mir die Gleichheit auch erklären. Ich bin halt verwundert, dass ich jetzt "für alle" c betrachte statt "ein" c
17.03.2023, 13:36	HAL 9000	Auf diesen Beitrag antworten »
Ehrlich gesagt ist mit die Schreibweise $\begin{eqnarray} f\in g\left(\mathcal{O}(h(n))\right) \end{eqnarray}$ nicht geläufig: Für streng monoton wachsende positive Funktionen $\begin{eqnarray} g \end{eqnarray}$ soll sie womöglich dasselbe ausdrücken wie $\begin{eqnarray} g^{-1}\circ f\in \mathcal{O}(h(n)) \end{eqnarray}$ ? Oder wie sonst definiert ihr das?
17.03.2023, 14:14	Malcang	Auf diesen Beitrag antworten »
Hallo HAL 9000, ehrlich gesagt haben wir das nicht definiert Wir haben wichtige Komplexitätsklassen folgendermaßen: [attach]56929[/attach] und eine Folgerung daraus ist [attach]56931[/attach] Nur aus dieser habe ich das geschlussfolgert, was ich oben geschrieben habe.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »