n * n (non imbriqué) pour la complexité de boucle

Question

Je sais que le modèle de complexité d'algorithme lorsque l'on regarde les boucles imbriquées est généralement n^(m+1), où m est le facteur d'imbrication de boucle (boucle dans une boucle).

Mais qu'en ce cas simple, où

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

est la complexité O(n^2)? Parce que la quantité d'exécutions est la même que pour une boucle for imbriquée normale.

Answer 1

En supposant que le travail effectué à chaque itération de la boucle for est O (1) alors la complexité de la boucle for est en effet O (n^2) puisque vous itérez n^2 fois. Et oui, vous supposez correctement qu'il serait de la même complexité que:

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