Ich hatte in
diesem Thread ein paar Verwirrungen bezüglich der Vereinfachungen von asymtotischen Komplexitäten bei mehreren Variablen. Mir ist klar geworden, dass die Zweideutigkeit nur dadurch entstehen konnte, dass die Landau-Symbole nur für jeweils eine Variable definiert wurde, obwohl wir oft mit mehreren Variablen zu tun haben. Wikipedia beschreibt, dass man diese reelle (bei uns natürliche) Variable samt ihrem Grenzwert zu einem topologischen Raum verallgemeinern könnte (in unserem Fall also \mathbb{N}^k). In unserem Fall, wo wir unsere Variablen immer gegen unendlich streben lassen, würde ich das so interpretieren, dass die Definition des Groß-O bei zwei Variablen n und m folgendermaßen aufgeschrieben werden kann:
Code: Alles auswählen
\begin{equation}
f \in \mathcal{O}(g) \Leftrightarrow (\exists c \in \mathbb{R}^+) (\exists n_0 \in \mathbb{N}) (\exists m_0 \in \mathbb{N}) (\forall n > n_0) (\forall m > m_0) \quad f(n,m) \leq c \cdot g(n,m)
\end{equation}
Eine andere Art, das zu verallgemeinern, was aber eine stärkere Behauptung wäre, ist die folgende:
Code: Alles auswählen
\begin{align}
f \in \mathcal{O}(g) \Leftrightarrow& (\exists c \in \mathbb{R}^+) (\exists n_0 \in \mathbb{N}) (\forall n > n_0) \quad f(n,m) \leq c \cdot g(n,m)\\
\wedge& (\exists c \in \mathbb{R}^+) (\exists m_0 \in \mathbb{N}) (\forall m > m_0) \quad f(n,m) \leq c \cdot g(n,m)
\end{align}
Diese zweite Definition würde bedeuten, dass im verlinkten Thread das + n nicht wegfallen würde. Da das laut Prof aber wegfällt, würde ich sagen, dass die erste Definition diejenige ist, mit der wir in der Vorlesung arbeiten, korrekt? Ich möchte um eine Bestätigung von offizieller Seite bitten.
Tut mir leid, dass ich den LaTeX-Code einfach so hingeknallt habe, aber die tex-Tags funktionieren in diesem Forum anscheinend nicht. Wer will, kann das ja in LaTeX kompilieren, dann kann man die Formeln ordentlich sehen.
