0 Daumen
483 Aufrufe

Ich soll zeigen bzw. begründen ob die folgende Eigenschaft gilt. Ich verstehe jedoch die Frage nicht.

\( 4 n^{3}+999 n^{2}=\Omega\left(n^{4}\right) \)
\( 5 n^{3}+321 n^{2}=\Theta\left(n^{2}\right) \)
\( \log _{10}(3 n)=\Theta\left(\log _{2}(n)\right) \)
\( 3^{n+1}=\Theta\left(3^{n}\right) \)
\( 5^{2 n}=O\left(5^{n}\right) \)
\( 77 n^{2}+3 n-\log _{5}(n)+\log _{2}(6 n)=O\left(n^{2}+\log _{10}(n)\right) \)

Vielleicht will mir jemand einen Denkanstoß geben was ich da jetzt genau machen muss...

Es geht darum wie Größenordnungsangaben verwendet werden, um die Komplexität von Algorithmen zu beschreiben.

Die Funktionssymbole Θ, Ω und Ο sind Notation aus der Informatik:

\( \mathrm{O}(g(n)): \) Menge aller Funktionen die, abgesehen von einem konstanten Faktor, für große Werte von \( n \) nicht stärker wachsen wie Funktion \( g(n) \)
\( \Omega(g(n)): \) Menge aller Funktionen, die, abgesehen von einem konstanten Faktor, für große Werte von \( n \) mindestens so stark wachsen wie Funktion \( g(n) \)
\( \Theta(g(n)) \) : Menge aller Funktionen, die, abgesehen von einem konstanten Faktor, für große Werte von n gleich stark wachsen wie Funktion \( g(n) \)

Das könnte für das Verständnis eventuell auch helfen:

\( f(n)=O(g(n)) \)
"f wächst asymptotisch höchstens so stark wie \( \mathrm{g}^{\prime \prime} \) "g ist asymptotische obere Schranke für das Wachstum von f"
\( \mathrm{f}(\mathrm{n})=\Omega(\mathrm{g}(\mathrm{n})) \)
"f wächst asymptotisch mindestens so stark wie \( \mathrm{g}^{\prime \prime} \)
"g ist asymptotische untere Schranke für das Wachstum von f"
\( \mathrm{f}(\mathrm{n})=\Theta(\mathrm{g}(\mathrm{n})) \)
"f wächst asymptotisch gleich stark wie \( \mathrm{g}^{\prime \prime} \)

Avatar von

Was heißt "wächst asymptotisch"? Die Stärke des Wachstums lässt sich über die ersten Ableitungen von f und g vergleichen. Da sieht nan sehr leicht, dass je nach Bereich f bzw. g stärker wächst. Aber so ist das wohl nicht gemeint.

1. Sicher, dass bei den Behauptungen Gleichheitszeichen und keine Elementzeichen gemeint waren? Ich sehe links allenfalls einzelne Elemente der Menge rechts.

2. Sehen die Wachstumssymbole so aus, wie du dir das vorgestellt hast?

Landau-Symbole vgl. Link im Kommentar hier https://www.mathelounge.de/621797/seien-f-r-wobei-i-r0-ein-intervall-zeige-1-f-g-o-h-min-p-q-fur-h . In der Informatik offenbar noch weitere Symbole.

Armagan hat gestern in einem Kommentar erklärt, dass die Symbole aus der Informatik bekannt sind und dann die Definitionen oben nachgeliefert. Vgl. allenfalls auch hiermit https://www.stacklounge.de/4893/weitere-asymptotische-laufzeitanalyse

Mathe53 hat € als Elementzeichen verwendet, das ist besser als das irreführende Gleichheitszeichen.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community