Différence pratique entre O (n) et O (1 + n)?

Question

O (n) n'est-il pas une amélioration par rapport à O (1 + n)?

C'est ma conception de la différence:

O (n):

for i=0 to n do ; print i ; 

O (1 + n):

a = 1; 
for i=0 to n do ; print i+a ; 

... qui vient réduire à Sur la droite?

Si la complexité du temps cible est O (1 + n), mais j'ai une solution dans O (n), cela signifie-t-il que je fais quelque chose de mal?

Merci.

Answer 1

O (1 + n) et O (n) sont mathématiquement identiques, comme vous pouvez le constater directement à partir du formal definition ou en utilisant la règle standard que O (a (n) + b (n)) est égal au plus grand de O (a (n)) et O (b (n)). En pratique, bien sûr, si vous faites n + 1 choses (en général, dépendantes des optimisations du compilateur/etc), cela prendra plus de temps que si vous ne faites que n choses. Mais la notation big-O est le mauvais outil pour parler de ces différences, car elle jette explicitement des différences comme ça.

Answer 2

O (n) n'est-il pas une amélioration par rapport à O (1 + n)?

Non, ce n'est pas le cas. Asymptotiquement, ces deux sont identiques. En fait, O (n) est identique à O (n + k) où k est une valeur constante.

Answer 3

Ce n'est pas une amélioration, car BigO ne décrit pas le temps exact de votre algorithme mais son taux de croissance . BigO décrit donc une classe de fonctions, pas une seule fonction. O(n^2) ne signifie pas que vos algorithmes pour l'entrée de la taille 2 se déroulera dans 4 opérations, cela signifie que si vous deviez tracer le temps d'exécution de votre application en fonction de n il serait asymptotiquement borne supérieure par c*n^2 à partir de certains n0 . C'est bien parce que nous savons à quel point notre algorithme sera plus lent pour chaque taille d'entrée, mais nous ne savons pas exactement à quelle vitesse il sera. Pourquoi utiliser le c? Parce que comme je l'ai dit, nous ne nous intéressons pas aux nombres exacts mais à la forme de la fonction - lorsque nous multiplions par un facteur constant, la forme reste la même.