Complexité temporelle dans la boucle

Question

Im nouveau avec analyse algorithmique. Je veux juste vérifier mi compréhension:

Par exemple:

for (i=0, i<n; i++) { 
} 

est clair qu'il ya 1 asignation, n comparations et n incrémentations.

La fonction n est égal à: T (n) = t0 + t1 * n + t2 * n = t0 + (t1 + t2) n = c0 + c1 * n

Ainsi, la complexité est la suivante: O (n)

Mais, dans ce cas, d'autres i besoin de quelques conseils:

for (i=0, i<=n; i++) { 
} 

T (n) = t0 + t1 * (n + 1) + t2 * (n + 1) ???

for (i=0, i<n-1; i++) { 
} 

T (n) = t0 + t1 * (n-1) + t2 * (n-1) ???

for (i=1, i<n; i++) { 
} 

T (n) = t0 + t1 * (n-1) + t2 * (n-1) ???

Je pense que l'on dirait que toutes ces boucles fors sont juste O (n) et c'est la seule chose qui compte. Mais je veux savoir si ces définitions de T (n) sont correctes.

Answer 1

Oui, ils sont tous O (n), et oui, vos équations pour T sont correctes.

En général, alors que T est utile pour se familiariser avec l'analyse de complexité, il n'est pas utilisé autrement. La plupart des gens sont préoccupés par le O d'un problème. En outre, une fois que vous avez trouvé un ensemble d'algorithmes avec O minimal (ou optimal), le problème de trouver le meilleur de cet ensemble dépend rarement de T. En effet, des choses comme, par exemple, la cohérence de la mémoire cache sont généralement plus importantes que le nombre absolu de comparaisons ou d'ajouts pour la plupart des problèmes pratiques.

Si vous prenez deux boucles:

for (i = 0; i < n; i++) {} 

et

for (i = 0; i <= n; i++) {} 

La boucle inférieure exécutera une fois de plus que celui du haut (il exécutera lorsque i == n, tandis que la boucle supérieure sautera ce). Ainsi, lors du calcul de l'exécution, ceux-ci sont différents. Le premier exécute la comparaison/incrément n fois exactement (lorsque i est {0,1,...,n-1}); le bas l'exécutera n+1 (lorsque i est {0,1,...,n-1,n}).

Cependant, en notation Big-O, vous recherchez comportement asymptotique - c'est-à-dire que ce qui se passe avec n est vraiment important. Et dans ce cas, vous ne prenez que le facteur n qui varie le plus rapidement. Lorsque n est très grand, l'itération supplémentaire de la boucle ci-dessus n'aura pas d'importance du tout, donc les deux boucles sont O(n).

Une chose importante à garder à l'esprit avec la notation Big-O est qu'elle ne capture absolument pas tout ce qui concerne un algorithme. C'est un bon premier passage - un algorithme qui est O(n) sera presque toujours meilleur que celui qui est O(n^3). Mais dans l'espace des algorithmes avec le même - ou presque le même - exposant, il peut y avoir des performances très différentes lorsqu'il est implémenté sur des systèmes réels.

Answer 2

O (n) signifie qu'il y a une constante M> 0 que le nombre d'opérations est < M * n. Donc dans votre cas c'est O (n) pour le second cas, on pourrait dire que c'est O (n-1) mais il est plus facile de dire que c'est O (n) car c'est exactement le même quand n -> infini.

n-1/n -> 1

Si T (n) est le nombre d'opérations exactes de sorte que vous ne pouvez pas simplifier le résultat