Pourquoi le Big-O de la complexité de cet algorithme en O(n^2)?

Question

Je sais que le big-O de la complexité de cet algorithme est - O(n^2), mais je ne comprends pas pourquoi.

int sum = 0; 
int i = 1; j = n * n; 
while (i++ < j--) 
  sum++;

Même si nous avons mis j = n * n au début, on incrémente i et de décrémentation j au cours de chaque itération, et donc ne devrait pas le nombre d'itérations-être beaucoup moins que n*n?

Answer 1

Au cours de chaque itération, vous incrément i et de décrémentation j qui est l'équivalent d'un peu incrémentation i par 2. Par conséquent, le nombre total d'itérations est n^2 / 2 et qui est toujours en O(n^2).

Answer 2

big-O complexité ignore les coefficients. Par exemple: O(n), O(2n), et O(1000n) sont tout de même O(n) de temps de fonctionnement. De même, O(n^2) et O(0.5n^2) sont à la fois O(n^2) de temps de fonctionnement.

Dans votre situation, vous êtes essentiellement l'incrémentation de votre compteur de boucle par 2 à chaque fois par le biais de votre boucle (depuis j-- a le même effet qu' i++). Si votre temps de marche est - O(0.5n^2), mais c'est le même que O(n^2) lorsque vous retirez le coefficient.

Answer 3

Vous aurez exactement n*n/2 itérations de boucle (ou (n*n-1)/2 si n est impair). Dans la notation grand O nous avons O((n*n-1)/2) = O(n*n/2) = O(n*n) car des facteurs constants "ne comptent pas".

Answer 4

Votre algorithme est équivalent à

while (i += 2 < n*n) 
  ...

qui est - O(n^2/2) qui est la même pour O(n^2) parce que big O la complexité ne se soucie pas des constantes.

Answer 5

Soit m le nombre d'itérations prises. Ensuite,

i+m = n^2 - m

ce qui donne,

m = (n^2-i)/2

En Big-O de notation, ce qui implique une complexité de O(n^2).