Wenn f = O(g) , ist e^f = O(e^g) ?
Ich habe die obige Frage schwer herausgefunden. Ein Beispiel wäre willkommen. Wenn Sie die Regel von l'Hôpital verwenden, zeigen Sie bitte, wie Sie die Differenzierung vornehmen.
Der Anspruch ist nicht korrekt.
Ein Gegenbeispiel ist das Folgende: Wir haben keinen Zweifel, dass 2n ein Element von O(n) ist. Aber wir können beweisen, dass exp(2n) kein Element von O(exp(n)) ist. Dies kann leicht durch die Berechnung der
was bedeutet, dass exp(2n) nicht in O(exp(n)) ist.
In Anbetracht Ihres Hinweises auf L'Hospital: Es ist eine Regel für die Berechnung von Limits mit Derivaten, genauer gesagt:
%Vor% unter bestimmten Umständen (zB sowohl f als auch g tendieren in Richtung Unendlichkeit. Ich kenne die genauen Kriterien nicht, die erfüllt werden müssen, daher empfehle ich nur, dies für weitere Informationen.
Aber was wir über Funktionen und deren Ableitungen sagen können, ist folgendes:
Wenn f'(x) ein Element von O(g'(x)) ist, dann haben wir f(x) ist ein Element von O(g(x)) . Die andere Richtung ist nicht der Fall.
Ich werde versuchen, Ihnen bei l'Hôpital zu helfen:
$ \ lim_ {x \ zu a} {f (x) \ über g (x)} = \ lim_ {x \ zu a} {f '(a) \ über g' (a)}
Wir benutzen das, um inf / inf oder 0/0 Unbestimmtheit zu lösen. Aber Ihr Problem ist nicht, dass ich denke, aber vielleicht, wenn Sie versuchen, die O (g (n)) oder exp (f (n)) abzuleiten, die zusammengesetzte Funktionen sind.
Die Kettenregel zum Ableiten von zusammengesetzten Funktionen lautet wie folgt: (fo g) (x) = f '(g (x)). g' (x)
Wenn Sie dem folgen, können Sie eine zusammengesetzte Funktion ableiten.
Tags und Links computer-science big-o