Comment puis-je prouver que 1/n est O (1)?

Question

Comment puis-je prouver mathématiquement que 1/n est O (1)? Je suis confus sur où commencer. De l'aide?

Answer 1

Si vous démontrez cela pour un algorithme, commencez en indiquant que l'entrée sera un montant positif de données (N> = 1), vous ne pouvez pas entrer les données 1/2 :)

Après cela, démontrer que 1/n est une fonction croissante quand n> 1, vous devriez utiliser l'induction sur cela, et vous êtes prêt à partir, parce que vous avez déjà souligné que n sera plus grand que 1 toujours!

Answer 2

Comme le dit le problème, commencez par la définition de la notation big-O.

F(x) = O(G(x)) IFF there exist constants k and m, 
such that for all n > m, k*|G(n)| > F(n). 

(Consultez votre textboox pour le libellé précis ici.)

Officieusement, cela signifie que si nous allons assez loin "out", par la suite G (n) dominera F (n), peu importe quel est l'avantage initial que nous donnons à F (n) via des facteurs constants.

---

Alors, comment pouvez-vous prouver quelque chose comme ça?

De telles preuves sont typiquement réalisées de manière constructive - en montrant que des valeurs bien choisies pour m et k font que l'inégalité fonctionne.

Maintenant vous faites juste de l'algèbre. Trouvez quelques m et k qui satisfont à la définition formelle. Selon le niveau de formalité/détail requis, vous devrez peut-être prouver que 1/n diminue de façon monotone (ou fait une preuve d'induction) pour montrer que votre choix de m et k fonctionne réellement.

---

Margus (et Loadmaster): notation Asymptotic parle de fonctions, et est complètement indépendant du matériel et la mise en œuvre sous-jacente. 1/n = O (1) est une vérité mathématique qui n'est pas fondée même sur l'existence de choses que nous appelons «ordinateurs». Si vous pensez au nombre d'instructions, vous raisonnez sur les classes de complexité (pensez P, NP, EXP), pas sur la notation asymptotique.

Answer 3

Vous n'avez pas à le prouver, c'est un fait. la limite supérieure de 1/n étant donné que n est un nombre naturel supérieur à 0 est toujours 1.

Answer 4

Eh bien, réfléchissons un instant. Nous avons deux fonctions f (n) = 1/n et g (n) = 1. Ce dont nous avons besoin est deux constantes C et k telles que 0 < = f (n) < = C * g (n) lorsque n> k. Si le domaine des deux fonctions est restreint à l'ensemble de tous les entiers positifs, on choisit simplement C = 2 et k = 0. Alors nous avons 0 < = 1/n < = 2 * 1 pour tout n> 0. Ici nous appelons C et k les témoins de la relation 1/n est O (1).

Besoin de le prouver un peu plus rigoureusement? Eh bien ... clairement 1/n si et seulement si n (par simple algèbre). Donc si n = 1 (ce qui signifie 1/n = 1) nous savons que 2 * 1> 1 et si n> 1 nous savons que cela implique 1/n < 1, auquel cas 2 * 1> 1/n.