si Je vais difficilement déterminer la question ci-dessus. Un exemple serait le bienvenu. En outre, si vous utilisez la règle de l'Hôpital, veuillez montrer comment vous faites la différenciation. f = o (g) est e ^ f = o (e ^ g) ?
3 Réponses :
Je vais essayer de vous aider avec l'Hôpital's:
$ \ lim_ {x \ à a} {f (x) \ over g (x)} = \ lim_ {x \ to a} {f '(a) \ over g' (a)}
Nous utilisons cela afin de résoudre INF / INF ou 0/0 indétermination. Mais votre problème n'est pas que je pense, mais peut-être que lorsque vous essayez de dériver le O (g (n)) ou d'exp (f (n)) qui sont des fonctions composites.
La règle de la chaîne pour dériver des fonctions composites est la suivante: (f o g) (x) = f '(g (x)). g' (x)
Si vous suivez cela, vous pouvez dériver n'importe quelle fonction composite.
Cette instruction est fausse, par exemple 2n = O (n), mais exp (2n)! = O (exp (n)). (Ce dernier signifierait EXP (2n) <= C Exp (n) pour suffisamment grand N, I.e. exp (n) <= C qui n'est pas vrai.)
C'est en effet un piège commun d'analyse asymptotique. Passe au logarithme (ou à une fonction dont le dérivé est délimité à l'infini) conserve BIG O cependant.
@Alexandre: Non, ça ne le fait pas. $ journal (n ^ 3) \ in o (log (n ^ 2)) $ . Notez également que 3 ^ n \ notin o (2 ^ n) $ . L'utilisation d'un logarithme trie vos fonctions en deux classes de complexité de base: le temps polynôme (logarithmes de tous les polynômes sont tous dans la même classe Big-O) et une heure exponentielle (les logarithmes de toutes les exponentielles sont toutes dans les mêmes Big-O classer).
@Ken: Oups ... d'accord, ça marche avec des équivalents: F ~ g => Log f ~ Log g d'où ma confusion!
Il y a un cas où cette affirmation est vraie: quand f (n) = g (n)
Votre réponse a du sens, mais contredit théorème 4 sur P5: CS.CMU.EDU/~JAMIEMMMT/TREACHING/SU-122/Lectures/07-bigo.pdf . Est-ce que ce théorème est incorrect?
@TwinLake Vous êtes correct. J'ai la même confusion. Quelqu'un peut-il s'il vous plaît reconnaître?
La réclamation n'est pas correcte.
Un conterExample est ce qui suit: nous n'avons aucun doute que qui implique que Compte tenu de votre indice d'hospitalisation: il s'agit d'une règle de limitation informatique utilisant des dérivés, plus précisément: Mais, ce que nous pouvons dire sur les fonctions et leurs dérivés sont les suivants: si 2n est élément de O (n) . Mais, nous pouvons prouver que exp (2n) n'est pas un élément de O (exp (n)) . Cela peut être facilement vu en calculant le exp (2n) n'est pas dans O (exp (N)) . f et g tendent vers l'infini. Je ne connais pas les critères exacts à remplir, donc je suggère simplement de lire Ce pour plus d'informations. f '(x) est élément de O (g' (x)) , alors nous avons ce f (x) est l'élément de o (g (x)) . L'autre sens n'est pas le cas.
Si vous googling, vous voudrez peut-être obtenir le droit de orthographe pour la règle de l'Hôpital , par exemple. en.wikipedia.org/wiki/l'HôPital's_rule
Cette question n'appartient-elle pas en maths?
math.stackexchange.com
@Zeta, je ne le pense pas, c'est fermement en CS.