O-Notation |
28.01.2019, 20:33 | Auf diesen Beitrag antworten » | ||
AP0 | O-Notation 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 |
||
|
|||
03.02.2019, 21:49 | Auf diesen Beitrag antworten » | ||
ed209 |
Wie ist denn die Definition der O-Notation? Gruss, ED |
|