Big-O notation trouver c et n0
J'ai juste été introduit pour Big-O notation et j'ai quelques questions. Cependant, je suis confus quant à la façon de déterminer la valeur de n0
.
Je dois montrer que 3n^3 +20n^2 + 5
est O(n^3). Pour l'instant j'ai:
3n^3 + 20n^2 + 5 <= cn^3
(3 - c)n^3 + 20n^2 + 5 <= 0
5 <= n^3(c - 3) - 20n^2
5 <= n^2(n(c - 3) - 20)
Je ne sais pas quoi faire à partir d'ici pour trouver n0 et c. Quelqu'un aurait l'esprit expliquant?
OriginalL'auteur Dom Brown | 2013-01-10
Vous devez vous connecter pour publier un commentaire.
Selon l'endroit où vous voulez le plus de condition pour commencer, vous pouvez maintenant choisir n0 et trouver la valeur.
Par exemple, pour n0 = 1:
Il est intéressant de noter que, de par la définition de Big-O de notation, il n'est pas nécessaire que le fait d'être serré. Puisque c'est une fonction simple, vous avez juste à deviner et vérifier (par exemple, choisir de 100 pour c et note que la condition est vrai asymptotiquement).
Par exemple:
Que l'inégalité holding vrai, c'est assez pour prouver que f(n) est O(n^3).
Pour offrir une meilleure preuve, il doit être démontré que les deux constantes,
c
etn0
existent, tels quef(n) <= cg(n) for all n > n0
.À l'aide de notre c = 28, c'est très facile à faire:
(C'est assez mal fait "preuve" mais j'espère que l'idée montre.)
Hrmmm, peut-être que j'ai mal compris ce que n0 est. n0 est le point où
3n^3 + 20n^2 + 5
etcn^3
se croisent, correct? Cette intersection est une fonction dec
(indirectement), donc il n'y a pas de solution unique pourn0
etc
.Mes notes de dire ceci: étant Donné les fonctions f(n) et g(n) nous disons que f(n) est O(g(n)) s'il existe des constantes positives c et n0 tel que f(n) ≤ cg(n) pour n ≥ n0
La droite. Big O n'a qu'à satisfaire à la condition asymptotiquement. Cela signifie que f(n) peut être > cg(n) pour une partie du domaine. C'est juste une fois un certain point est atteint (ce point étant appelé
n0
ici), f(n) doit être >= cg(n). Pour prouver le Big-O de la relation, tout ce que vous avez à faire est de prouver l'existence dec
etn0
. (Il est intéressant de noter que, dans ma réponse, je n'ai pas techniquement prouver leur existence. Je vais modifier ma réponse dans un instant.)Je vous remercie pour l'aide. Il y a juste une chose que je voudrais éclaircir. Est-il possible d'avoir plusieurs réponses à cette question? c'est à dire il pourrait y en avoir deux autres valeurs de n0 et c?
OriginalL'auteur Corbin
Je crois qu'il devrait être c>=2?
5 > 2 donc ce n'est pas du tout différent. Tout n0 et tout c qui détient sont tout à fait bien.
OriginalL'auteur perreal
Si vous avez
f(n) = (3n^3 + 20n^2 + 5)
et vous voulez voir si c'estO(g(n))
oùg(n) = n^3
, je crois que vous pouvez prendre à la limite def(n)/g(n)
que la n->infini.Parce que la limite est de 3, vous pouvez voir que
3n^3 + 20n^2 + 5
seulement se développe aussi rapidement quen^3
. Lorsque vous avez un polynôme comme3n^3 + 20n^2 + 5
, vous pouvez dire par l'inspection que la plus grande commande terme sera toujours la valeur deO(f(n))
.Ce n'est pas beaucoup d'aide pour trouver n0 et C, mais c'est un moyen relativement simple de déterminer ce que la commande de quelque chose. Comme les autres l'ont dit ici, il vous suffit de prendre n0 et ensuite calculer C.
Si vous choisissez n0 = 1, alors vous avez
3*(1^3) + 20*1^2 + 5 = 28
. Donc, sic1^3 <= 28
, c est de 28. Vous ai montré il y a là un c et n0 qui répond à cette condition, de sorte que vous avez prouvé f(n) est O(n^3)OriginalL'auteur munk
Diviser par n^3
nous obtenons
3+20/n+5/n^3<=C
20/n+5/n^3<=C-3
De prendre C valeur de 10
20/n+5/n^3<=7
Nous avons besoin pour résoudre ce pour différentes valeurs de n jusqu'à ce que la condition devient satisfait
C=10 et n0 = 3 donnera la solution
OriginalL'auteur user6027109