Comment trouver la complexité de ce code selon la notation Big O?

Question

J'ai trouvé ce code dans mon livre d'algorithmes mais je n'ai pas compris l'exemple.

Voici le code:

for(i=1;i<n-1;i++){ 
    for(j=n;j>i+1;j--){ 
     if(a[j-1]>a[j]){ 
     t=a[j-1]; 
     a[j-1]=a[j]; 
     a[j]=t; 
    } 
    } 
} 

maintenant et selon le livre de la complexité de la chaque partie calculée comme celui-ci

et aussi le grand O du code entier calculé comme

Mais je ne pouvais pas le comprendre. Pouvez-vous s'il vous plaît expliquer la complexité du code pour moi? en particulier la partie où il a calculé la complexité comme O(n/2) en raison du terme j>i+1

désolé pour mon anglais.

Answer 1

Des questions comme celles-là semblent assez fréquentes. Voici votre code swapping:

for (i=1; i < n-1; i++) { 
    for (j=n; j > i+1; j--) { 
     if (a[j-1] > a[j]) { 
      t = a[j-1]; 
      a[j-1] = a[j]; 
      a[j] = t; 
     } 
    } 
} 

que la boucle Appreciate extérieure prendra N-1 étapes. La boucle interne prendra entre N-2 et 1 étapes. Nous pouvons approximer cela plus loin en disant que la boucle externe a N étapes et la boucle interne prendra entre 1 et N étapes. En moyenne, alors, la boucle interne prendra N/2 étapes à compléter. Ceci correspond à O(N*N/2) = O(N^2). Donc, le code d'échange que vous nous avez montré est O(N^2).

Answer 2

La boucle externe exécute i = 1 à n-2, c'est-à-dire n-2 fois. La boucle interne exécute (n-3), (n-4), ......, n- (n-1) qui est au total n-3 + n-4 + n-5 + ... + 2 + 1 fois. Quand i = 1 boucle interne s'exécute (n-3) fois, quand i = (n-2) boucle interne exécute 1 fois. Cela donnera (n-3) (n-2)/2. Quand on considère la condition if et son corps, pour chaque exécution de la boucle interne, 3 instructions sont exécutées. Au total cela donnera (n-3) (n-2)/2 * 3. Il n'y a pas besoin de considérer (n-3) comme (n-3), au contraire le prendre comme n et ne pas considérer ** 3 et/2. Le calcul de la complexité à l'aide d'une telle méthode est une approximation. La complexité est donc de l'ordre de n * n. O (n^2). Lorsque vous voyez une boucle, considérez-la comme n étapes.

S'il y a des boucles intérieures, multipliez-les. Pour une boucle O (n). Pour deux boucles O (n * n). Pour trois boucles O (n ** n * n), etc.