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

Informatiker Board » Themengebiete » Theoretische Informatik » Berechenbarkeits- und Komplexitätstheorie » O-Notation » 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
Autor
Beitrag « Vorheriges Thema | Nächstes Thema »
AP0
Grünschnabel


Dabei seit: 28.01.2019
Beiträge: 1

O-Notation 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 zusammen,
ich habe eine Frage zur O-Notation bzw. eine Aufgabe, bei der ich nicht so recht weiter weiß:

Beweisen Sie die folgende Ungleichung. Zu einem korrekten Beweis gehört die Angabe einer Konstante c und eines N, sodass für alle
n >= N gilt: f(n) < c*g(n).
Hinweis: Benutzen Sie die die Definition der O-Notation und vollständige Induktion.
a) O(2^n) < O(n!).

Was mir hier noch nicht völlig klar ist, sind die Konstanten N und c. Wie in der Aufgabe steht, soll ja für alle n >= N gelten: f(n) < c*g(n).
Aber bedeutet das nicht, dass N davon abhängt, wie c gewählt ist? Bzw. wie würde ich hier mit der Induktion starten?
Ich hoffe, dass ihr mir helfen könnt smile
28.01.2019 20:33 AP0 ist offline Beiträge von AP0 suchen Nehmen Sie AP0 in Ihre Freundesliste auf
ed209
Routinier


Dabei seit: 07.09.2006
Beiträge: 317

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:

Hinweis: Benutzen Sie die die Definition der O-Notation und vollständige Induktion.


Wie ist denn die Definition der O-Notation?

Gruss,
ED
03.02.2019 21:49 ed209 ist offline E-Mail an ed209 senden Beiträge von ed209 suchen Nehmen Sie ed209 in Ihre Freundesliste auf
Baumstruktur | Brettstruktur
Gehe zu:
Neues Thema erstellen Antwort erstellen
Informatiker Board » Themengebiete » Theoretische Informatik » Berechenbarkeits- und Komplexitätstheorie » O-Notation