Registrierung Kalender Mitgliederliste Teammitglieder Suche Häufig gestellte Fragen Zur Startseite

Informatiker Board » Themengebiete » Theoretische Informatik » Berechenbarkeits- und Komplexitätstheorie » Effizinez begründen » Hallo Gast [Anmelden|Registrieren]
Letzter Beitrag | Erster ungelesener Beitrag Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen
Neues Thema erstellen Antwort erstellen
Zum Ende der Seite springen Effizinez begründen
Autor
Beitrag « Vorheriges Thema | Nächstes Thema »
hallo123
unregistriert
Effizinez begründen Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

Meine Frage:
Die Algorithmen A,B und C haben die Zeitkomplexität tA(n), tB(n), tC(n). Ferner gilt tA(n) elementvon O(tB(n)) und tA(n) elementvon GroßOmega (tC(n)). Welche der folgenden Einschätzungen sind allein aufgrund dieser Aussagen angebracht und welche nicht?
a) A ist effizienter als B.
b) B ist nicht effizienter als A
c) A ist effizienter als B
d) A ist nicht effizienter als C

Meine Ideen:
Aussagen b und d sollen richtig sein, aber ich wüsste nicht warum. Kann mir jemand dabei helfen.
15.08.2018 13:38
as_string as_string ist männlich
Haudegen


Dabei seit: 06.11.2013
Beiträge: 631
Herkunft: Heidelberg

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

Hallo!

Soll das so aussehen?
[latex]t_A(n); t_B(n); t_C(n)[/latex]
Besonders das O, ist das das hier oder ist es ein kleines?
[latex]t_A(n) \in \mathcal{O}(t_B(n))[/latex]
[latex]t_A(n) \in \Omega(t_C(n))[/latex]

Gruß
Marco
19.08.2018 22:30 as_string ist offline E-Mail an as_string senden Beiträge von as_string suchen Nehmen Sie as_string in Ihre Freundesliste auf
as_string as_string ist männlich
Haudegen


Dabei seit: 06.11.2013
Beiträge: 631
Herkunft: Heidelberg

RE: Effizinez begründen Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

Zitat:
Original von hallo123
c) A ist effizienter als B

Das soll wohl heißen "c) A ist effizienter als C", so zumindest in Deinem ersten Post. So wie Du es hier geschrieben hast, wäre a) und c) ja sonst identisch.

Gruß
Marco
19.08.2018 23:02 as_string ist offline E-Mail an as_string senden Beiträge von as_string suchen Nehmen Sie as_string in Ihre Freundesliste auf
as_string as_string ist männlich
Haudegen


Dabei seit: 06.11.2013
Beiträge: 631
Herkunft: Heidelberg

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

Naja, wenn Du Dir die Beschreibungen auf der Wikipedia-Seite zu den Landau-Symbolen anschaust, sollte es klar werden, denke ich.
Hast Du die Definitionen mal verstanden? Frag bitte konkreter nach, wo Du nicht weiter kommst.

Gruß
Marco
19.08.2018 23:06 as_string ist offline E-Mail an as_string senden Beiträge von as_string suchen Nehmen Sie as_string in Ihre Freundesliste auf
Baumstruktur | Brettstruktur
Gehe zu:
Neues Thema erstellen Antwort erstellen
Informatiker Board » Themengebiete » Theoretische Informatik » Berechenbarkeits- und Komplexitätstheorie » Effizinez begründen