Matroids Matheplanet Forum Index
Moderiert von matroid
Informatik » Algorithmen / Datenstrukturen » Komplexitätsklassen - O-Notation
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Komplexitätsklassen - O-Notation
PshPsh
Neu Letzter Besuch: im letzten Monat
Dabei seit: 10.12.2020
Mitteilungen: 3
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StefanVogel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 26.11.2005
Mitteilungen: 3847
Wohnort: Raun
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
PshPsh
Neu Letzter Besuch: im letzten Monat
Dabei seit: 10.12.2020
Mitteilungen: 3
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2021-04-12


Vielen dank!!! :-)
2021-04-11 08:10 - StefanVogel in Beitrag No. 1 schreibt:
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




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
PshPsh hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


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]