Matroids Matheplanet Forum Index
Moderiert von matroid
Informatik » Algorithmen / Datenstrukturen » Komplexitätsklassen - O-Notation
Autor
Universität/Hochschule Komplexitätsklassen - O-Notation
PshPsh
Neu Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 10.12.2020
Mitteilungen: 3
  Themenstart: 2021-04-11

Guten Morgen, ich habe etwas Probleme, zu erkennen, wann welche Schranke eine Teilmenge, bzw. echte Teilmenge einer anderen Schranke ist. Die Aussage O(n^2 + n^2) ⊂ O(n^3) würde ich als richtig einschätzen. Aber die Aussage Θ(2^n) ⊆ Ω (2^n) wäre doch falsch, oder? Weil wenn die Komplexität genau 2^n ist, dann kann sie doch nicht eine Teilmenge von einer unteren Schranke 2^n sein, oder? Genau so die Aussage Θ(2^n) ⊆ O(2^n). Die genaue Komplexität 2^n ist doch nicht Teilmenge einer oberen Schranke 2^n. Oder: Θ(n^4 * log n) ⊆ Ω(n^4). Diese Aussage wäre richtig, oder? Denn die genaue Komplexität mit n^4 * log n wäre ja größer als die untere Schranke n^4, somit Teilmenge von der unteren Schranke n^4, oder? Und noch eine Verständnisfrage: Damit eine Funktion Element einer unteren Schranke ist, muss sie ja größer gleich dieser unteren Schranke sein. Aber bei der Funktion (log(n))/2 ELEMENT Ω(log(n)) würde diese Aussage ja stimmen, oder? denn sowohl log(n) ELEMENT Θlog(n) und auch (log(n))/2 ELEMENT Θlog(n), somit würden sie doch asymptotisch gleich wachsen, oder? Über tipps würde ich mich freuen! Liebe Grüße


   Profil
StefanVogel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 26.11.2005
Mitteilungen: 3930
Wohnort: Raun
  Beitrag No.1, eingetragen 2021-04-11

Hallo PshPsh, die erste Aussage stimmt. Die zweite und dritte musst du nochmal anschauen: Es gilt Θ(f) ⊆ Ω (f) und Θ(f) ⊆ O(f), siehe de.wikipedia.org/wiki/Landau-Symbole#Folgerung. Damit f ∈ Ω (g) gilt, muss nicht f ≥ g sein, wenn du das mit "größer gleich dieser unteren Schranke" meinst. Es gilt zum Beispiel auch f/2 ∈ Ω (f). Viele Grüße, Stefan


   Profil
PshPsh
Neu Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 10.12.2020
Mitteilungen: 3
  Beitrag No.2, vom Themenstarter, eingetragen 2021-04-12

Vielen dank!!! :-) \quoteon(2021-04-11 08:10 - StefanVogel in Beitrag No. 1) Hallo PshPsh, die erste Aussage stimmt. Die zweite und dritte musst du nochmal anschauen: Es gilt Θ(f) ⊆ Ω (f) und Θ(f) ⊆ O(f), siehe de.wikipedia.org/wiki/Landau-Symbole#Folgerung. Damit f ∈ Ω (g) gilt, muss nicht f ≥ g sein, wenn du das mit "größer gleich dieser unteren Schranke" meinst. Es gilt zum Beispiel auch f/2 ∈ Ω (f). Viele Grüße, Stefan \quoteoff


   Profil
PshPsh hat die Antworten auf ihre/seine Frage gesehen.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]