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

Informatiker Board » Themengebiete » Theoretische Informatik » Berechenbarkeits- und Komplexitätstheorie » O-Notation Beispiele mit Begründung » 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 O-Notation Beispiele mit Begründung
Autor
Beitrag « Vorheriges Thema | Nächstes Thema »
niete123
unregistriert
O-Notation Beispiele mit Begründung 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) ? O(tB(n)) und tA(n) ? ? (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 C
d) A ist nicht effizienter als C.

Meine Ideen:
b und d sollen richtig sein und a und c nicht, weil alle Algorithmen nicht gleich effizient sein können.
Kann mir jemand erklären weshalb und warum diese Aussagen b und d richtig sein können und warum die beiden Aussagen falsch sind
15.08.2018 13:23
as_string as_string ist männlich
Haudegen


Dabei seit: 06.11.2013
Beiträge: 634
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

Ich kann den Aufgabentext nicht lesen. Die Sonderzeichen werden als Fragezeichen dargestellt, so dass man nicht weiß, was gegeben ist.

Gruß
Marco
16.08.2018 14:43 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 » O-Notation Beispiele mit Begründung