Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Komplexitätstheorie » Wachstum von Funktionen: O-Notation und Omega-Notation
Autor
Universität/Hochschule Wachstum von Funktionen: O-Notation und Omega-Notation
danTheMano
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 02.07.2020
Mitteilungen: 9
  Themenstart: 2020-07-16

Hallo ich bräuchte Hilfe bei dieser Aufgabe. Meine Vermutung ist, dass man diese Aufgabe widerlegen kann da die Klassen O und Omega in keiner Relation sind, doch weiß leider nicht wie ich das genau beweisen kann. Ich bedanke mich schonmal für jede Antwort https://matheplanet.com/matheplanet/nuke/html/uploads/b/53344_Bildschirmfoto_2020-07-16_um_00.24.16.png


   Profil
ochen
Senior Letzter Besuch: im letzten Quartal
Dabei seit: 09.03.2015
Mitteilungen: 3407
Wohnort: der Nähe von Schwerin
  Beitrag No.1, eingetragen 2020-07-16

Hallo \quoteon(2020-07-16 00:30 - danTheMano im Themenstart) [...] da die Klassen O und Omega in keiner Relation sind, \quoteoff Doch, sie haben schon sehr etwas miteinander zutun. Wie habt ihr sie definiert? \quoteon doch weiß leider nicht wie ich das genau beweisen kann. \quoteoff Wenn du glaubst, dass die Aussage falsch ist, genügt es drei Funktionen $f,g$ und $h$ mit $h\in\Omega(f)$, $h\in\mathcal{O}(g)$ und $f\notin\Omega(g)$ zu finden und nachzuweisen, dass sie diesen Ansprüchen genügen. Es müssen also Konstanten $N,C_1,C_2>0$ mit \[ C_2 |g(n)|\leq |h(n)|\leq C_1|f(n)| \] für alle $n\geq N$ existieren. ...


   Profil
danTheMano
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 02.07.2020
Mitteilungen: 9
  Beitrag No.2, vom Themenstarter, eingetragen 2020-07-16

Hallo danke für die Antwort wir haben die wie im Bild definiert: https://matheplanet.com/matheplanet/nuke/html/uploads/b/53344_Bildschirmfoto_2020-07-16_um_17.26.15.png


   Profil
ochen
Senior Letzter Besuch: im letzten Quartal
Dabei seit: 09.03.2015
Mitteilungen: 3407
Wohnort: der Nähe von Schwerin
  Beitrag No.3, eingetragen 2020-07-16

Super, welche Schlussfolgerungen ziehst du daraus? Du kannst auch erstmal versuchen die Aussage zu zeigen. Wenn du dann nicht weiterkommst, dann findest du auch ein Gegenbeispiel. Wenn du aber damit durchkommst, ist die Aussage wohl richtig.


   Profil
danTheMano
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 02.07.2020
Mitteilungen: 9
  Beitrag No.4, vom Themenstarter, eingetragen 2020-07-16

das ist ja momentan mein Problem.. ich weiß nicht genau wie ich das zeigen kann bis jetzt habe ich nur die Definition https://matheplanet.com/matheplanet/nuke/html/uploads/b/53344_Bildschirmfoto_2020-07-16_um_18.05.19.png


   Profil
ochen
Senior Letzter Besuch: im letzten Quartal
Dabei seit: 09.03.2015
Mitteilungen: 3407
Wohnort: der Nähe von Schwerin
  Beitrag No.5, eingetragen 2020-07-16

Die Definitionen sind völlig ausreichend. Was heißt es, dass der Schnitt nicht leer ist? Das habe ich versucht in Beitrag 1 anzudeuten? Dann nutze die Definitionen. Setze $N:= \max\{n_{0,f},n_{0,g}\}$.


   Profil
danTheMano
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 02.07.2020
Mitteilungen: 9
  Beitrag No.6, vom Themenstarter, eingetragen 2020-07-16

ja es heißt, dass es keine leere Menge sein kann


   Profil
ochen
Senior Letzter Besuch: im letzten Quartal
Dabei seit: 09.03.2015
Mitteilungen: 3407
Wohnort: der Nähe von Schwerin
  Beitrag No.7, eingetragen 2020-07-16

Ja, das steht ja da. Ist $\{1,3\}\cap \{3,5\}$ die leere Menge? Warum? Warum nicht? Nun zu deiner Aufgabe: Sei $\ldots\cap\ldots\neq\emptyset$, so gibt es eine Funktion $h\colon \mathbb N\to\mathbb R_+$ mit ...


   Profil
danTheMano hat die Antworten auf ihre/seine Frage gesehen.
danTheMano wird per Mail über neue Antworten informiert.

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]