Selon la définition de Big O F (n) (ce qui signifie f (n) = O (g (n) code> ), on pourrait en déduire que: f(n) = 1 - 1 / n
f(n) = 2 - 1 / n
C = 1
8 Réponses :
o (1) et O (2) sont les mêmes, comme tout o (valeur constante).
Le point qui ne s'appuie pas non plus sur une fonction de n.
Il n'y a pas de différence entre formellement, envisagez une fonction O (1) et O (2) . Les algorithmes classant comme O (1) sont o (2) et inversement. En fait, O (c1) est O (c2) pour toute constantes positive C1 et c2 .
o (c) où c est une constance positive signifie simplement que le temps d'exécution est borné indépendamment de la taille d'entrée ou du problème. À partir de celui-ci, il est clair (de manière informelle) que O (1) et O (2) est égal.
f dans o (1) . Ensuite, il y a une constante C telle que f (n) <= c * 1 pour tous n . Laissez d = c / 2 . Alors f (n) <= c = (c / 2) * 2 = d * 2 qui montre que f est o (2) . De même si g est O (2) Il y a une constante C tel que g (n) <= c * 2 pour tous n . Laissez d = 2 * c . Alors g (n) <= c * 2 = d = d * 1 qui montre que g est o (1) . Par conséquent, O (1) = O (2) .
Vous n'écrivez généralement pas O (2) ou O (2n) mais O (1) et O (n) à la place. La différence est en vitesse réelle, bien sûr - 5s vs 10s par exemple. J'ai trouvé votre question un peu déroutant.
Non, Big-OH ne vous dit pas d'exécution et O (2) ne signifie certainement pas deux fois plus tard que O (1) .
Eh bien, il a raison qu'un algorithme qui effectue des opérations 2n prendra deux fois plus de temps qu'une opération qui prend des opérations n (en supposant que toutes les opérations prennent le même temps). Bien sûr, «deux fois plus longtemps» lorsque nous parlons de millisecondes, ce n'est pas une affaire si grosse, mais quand vous carré Ce numéro peut être assez gros, assez rapide.
Bien, je le sais et je ne l'explique pas bien. Cependant, j'essayais de deviner ce que l'asserveilleux voulait. Une réponse pédalette n'est pas toujours la meilleure réponse.
@Mark: Tout d'abord, vous supposez que toutes les opérations exécutées dans le même temps. Plus important encore, il n'a pas dit d'algorithme qui effectue des opérations 2n . Il comparé o (n) à o (2n) . Il existe des constantes cachées enterrées dans ces définitions qui signifient qu'ils ne traduisent pas directement "nombre d'opérations". En outre, lorsque nous parlons de Big-Oh, nous parlons souvent de cas moyen ou de pire des cas, par exemple, de manière à ce que vous ne puissiez plus directement traduire O (n) en "exécute n < / code> opérations. "
Il n'y a pas de différence entre O (1) et O (2).
L'ordre de la notation est unique à une constante. O (f ( x )) signifie qu'il y a une constante k de telle sorte que le temps serait inférieur à k f ( x x ).
Si quelque chose est O (2), il y a une constante k que le programme prend moins de 2 k . Par conséquent, il y a une autre constante, k '= 2 k qui fonctionne pour O (1).
Il n'y a pas de différence entre O (1) et O (2). En fait, vous n'utiliseriez pas cette notation. Il ressemble plus à O (n) ou O (n ^ 2), O (log (n)), etc. Il s'agit simplement d'une indication de l'ordre de grandeur de l'algorithme. Mettre en d'autres termes, o (1) serait constant à temps. O (n) serait linéaire dans le nombre d'éléments (n), O (n ^ 2) serait exponentiel dans le temps, etc.
O (n ^ 2) n'est pas exponentiel; Il est quadratique dans le temps. O (2 ^ n) est un exemple de temps exponentiel.
Peut-être qu'ils signifiaient que les deux algorithmes s'exécutent en temps constant, quelle que soit la taille d'entrée (généralement indiquée par n), mais l'une d'entre elles est deux fois plus rapide. Mais c'est un abus de la notation Big-O.
La notation Big-O est généralement utilisée pour l'analyse asymptotique de la complexité des algorithmes, c'est-à-dire une analyse de la manière dont l'algorithme fonctionne comme n augmente à l'infini. Le terme d'ordre le plus élevé dans N de la fonction F (n) sera la partie dominante de la fonction dans ce cas.
En tant que tel, les termes de l'ordre inférieur en n sont généralement supprimés de la fonction lorsqu'il est exprimé en Big-o (par exemple, F (N) = 2N ^ 2 + 4 entraînera O (n ^ 2) asymptotique big-o complexité).
Dans le cas du plus haut terme étant constant et non dépendant de n, alors toutes ces constantes sont effectivement les mêmes asymptotiquement et sont généralement simplement réduites à O (1).
Par conséquent, O (2) serait considéré comme équivalent à O (1).
Dans le graphique ci-dessous, la ligne rouge représente O (n) et la courbe verte représente O (n 2 ).
Comme vous pouvez le voir par la ligne rouge, le 
2 et le 1 devient insignifiant comme x augmente (la courbe verte grandit à un beaucoup plus rapide). C'est ce que la notation Big-O tente de capturer; constantes sont relativement dénuées.
Idéalement, O (2) n'existe pas, si cela devrait s'appeler O (1). Commande / O indique combien il dépend de l'entrée 'n'. Donc si cela ne dépend pas de n son o (1)
@Xinus: Non,
O (2) existe. Nous écrivons habituellement "o (1) " à la place.La fonction 2 est un élément de la série O (1), je crois