Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Komplexitätstheorie » Wachstum von Funktionen: O-Notation und Omega-Notation
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Wachstum von Funktionen: O-Notation und Omega-Notation
danTheMano
Junior Letzter Besuch: im letzten Monat
Dabei seit: 02.07.2020
Mitteilungen: 9
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-07-16 00:30


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




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
ochen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 09.03.2015
Mitteilungen: 2876
Aus: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-07-16 10:46


Hallo

2020-07-16 00:30 - danTheMano im Themenstart schreibt:
[...] da die Klassen O und Omega in keiner Relation sind,

Doch, sie haben schon sehr etwas miteinander zutun. Wie habt ihr sie definiert?


doch weiß leider nicht wie ich das genau beweisen kann.

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. ...



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
danTheMano
Junior Letzter Besuch: im letzten Monat
Dabei seit: 02.07.2020
Mitteilungen: 9
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2020-07-16 17:26


Hallo danke für die Antwort
wir haben die wie im Bild definiert:



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
ochen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 09.03.2015
Mitteilungen: 2876
Aus: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2020-07-16 17:41


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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
danTheMano
Junior Letzter Besuch: im letzten Monat
Dabei seit: 02.07.2020
Mitteilungen: 9
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2020-07-16 18:06


das ist ja momentan mein Problem.. ich weiß nicht genau wie ich das zeigen kann
bis jetzt habe ich nur die Definition



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
ochen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 09.03.2015
Mitteilungen: 2876
Aus: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2020-07-16 18: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}\}$.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
danTheMano
Junior Letzter Besuch: im letzten Monat
Dabei seit: 02.07.2020
Mitteilungen: 9
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2020-07-16 18:21


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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
ochen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 09.03.2015
Mitteilungen: 2876
Aus: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2020-07-16 18:37


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 ...



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
danTheMano hat die Antworten auf ihre/seine Frage gesehen.
danTheMano wird per Mail über neue Antworten informiert.
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-2020 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]