Comment cet algorithme de base est-il O (n)?

int G(int a[], int n) { int x=0, i, j; for(i=1; i<n; i=i*2){ for(j=0; j<i; j++) x += a[j]; } return x; } 

Comment est le pire des cas serré sur cet algorithme O (n). La première boucle n’est-elle pas exécutée O (log (n) fois et la seconde pour la boucle exécutée O (n) fois donnant O (n logn)?

O ( n ) signifie qu’un algorithme nécessite au plus un nombre d’étapes proportionnel à n lorsque sa taille en entrée est n . La boucle interne est O ( n ) dans cette caractérisation, mais sa taille en entrée est i , elle nécessite donc un certain nombre d’étapes proportionnelles à i .

Additionnez le nombre d’itérations de la boucle interne effectuées. Si n est exactement une puissance de deux, c’est 1 + 2 + 4 + 8 +… + n/2 . La sum de cette série est n-1 . Ainsi, l’ensemble du programme effectue n-1 itérations lorsque sa taille en entrée est n . Donc c’est O ( n ).

(Si n n’est pas exactement une puissance de deux, le nombre d’itérations est p-1 , où p est la plus petite puissance de 2 pas moins que n . p-1 est inférieur à 2*n , ce qui est proportionnel à n , donc le programme est toujours O ( n ).)