Je peux clairement voir que N ^ 2 est limité par C2 ^ N, mais comment puis-je le prouver en utilisant une définition formelle de Big-o. Je peux simplement le prouver par M.I.
Voici ma tentative .. Par définition, là-bas pour tout N> N0, il existe une constante C qui f (n) <= cg (n) où f (n) = n ^ 2 et g (n) = 2 ^ n
Devrais-je prendre la consignation des deux côtés et résoudre C?
Et une autre question sur la séquence Fibonacci, je veux résoudre la relation de récurrence. L'équation est ..
alors et un de plus
alors j'ai commencé à perdre de l'équation générale i
Le motif est en quelque sorte comme un triangle Pascal?
3 Réponses :
Comme vous le soulignez, pour voir si f (x) ε o (g (x)) vous devez trouver ...
tel que f (x) Dans ce cas, vous pouvez choisir c = 1 et x 0 = 2 . Ce que vous devez prouver est que
x 2 <2 x pour tous x> 2
À ce stade, vous pouvez connecter les deux côtés (car si le journal ( x )> journal ( y ), puis x> y . ) En supposant que vous utilisiez le journal de base-2, vous obtenez le suivant
log (x 2 ) et par lois standard des logarithmes, vous obtenez
2 · journal (x) depuis log (2) = 1 cela peut être écrit comme
2 · journal (x) Si nous définissons x = 2, nous obtenons
2 · journal (2) = 2
et puisque x pousse plus vite que log (x) nous savons que 2 · journal (x)
Parce que pour x = 2, nous avons 2 * journal (2) = 2 ≤ 2 et journal (x) poussent plus vite que x .
Mais "Log (x) pousse plus vite que X" est la déclaration que nous voulons prouver raison? Nous voulions prouver que "2 ^ n grandit plus vite que n ^ 2".
(Tout d'abord, désolé d'avoir été "x pousse plus vite que cock (x)" dans mon dernier commentaire.) Quoi qu'il en soit, je pense que vous pouvez prendre ce fait pour acquis.
Pour améliorer la réponse acceptée:
Vous devez prouver que x ^ 2 <2 ^ x pour tous x> 2
Prendre la connexion des deux côtés, nous devons prouver que:
2 · Log (x) Ainsi, nous devons montrer la fonction H (x) = x-2 · journal (x)> 0 pour tous x> 2
h (2) = 0
Différencier H (x) par rapport à X, nous obtenons H '(x) = 1 - 1 / (x · ln (2))
pour tous les x> 2, h '(x) est toujours supérieur à 0, donc h (x) continue d'augmenter et puisque h (2) = 0,
il est donc prouvé que h (x)> 0 pour tous x> 2,
ou x ^ 2 <2 ^ x pour tous x> 2
Pour la plupart, la réponse acceptée (d'Aioobe) est correcte, mais une correction importante doit être faite.
oui, pour x = 2, 2 × journal (x) = x ou 2 × journal (2) = 2 est correct, mais il implique de manière incorrecte que 2 × journal (x) Prenons x = 3, l'équation devient donc: 2 × journal (3) <3 (une équation invalide).
Si vous calculez cela, vous obtenez: 2 × journal (3) ≈ 3.16993 supérieur à 3.
Vous pouvez clairement voir cela si vous tracez f (x) = x 2 et g (x) = 2 x ou si vous tracez f (x) = 2 × journal (x) et g (x) = x (si c = 1).
entre x = 2 et x = 4, vous pouvez voir que g (x) plongera ci-dessous f (x). Il n'est que lorsque x ≥ 4, que f (x) restera ≤ C × g (x).
Donc, pour obtenir la bonne réponse, vous suivez les étapes décrites dans la réponse d'Aioobe, mais vous tracez les fonctions pour obtenir le dernier intersection de la dernière où f (x) = c × g (x ) . Le X à cette intersection est votre x 0 (avec le choisi C) pour lequel ce qui suit est vrai: f (x) ≤ c × g (x ) pour tous x ≥ x 0 . .
Donc pour C = 1, il devrait être: pour tous x≥4, ou x 0 = 4 
Meilleure demande ici .
o .. alors devrais-je deler le message ici?
Une solution consiste à utiliser une limite comme n approche à l'infinité de g (n) / f (n)
Cela vous dérangerait-il d'expliquer un peu plus en détail? 2 ^ N / N ^ 2 Comme 2 ^ N poussent plus vite que N ^ 2, lorsque N tend que l'infini g (n) / f (n) a également tendance à l'infini, non?