complexité Temps code donné

Question

Quelle est la complexité temporelle de ce code qui échanger a[i,j] avec a[j,i] pour j > i (transposent la matrice donnée):

for(i=1;i<=(n-1);i++) 
{ 
    for(j=(i+1);j<=n;j++) 
    { 
     T=a[i,j]; 

     a[i,j]=a[j,i]; 

     a[j,i]=T; 
    } 
} 

Answer 1

La boucle interne fonctionne en diminuant de n à 1, et le travail en cours (échange de nombres) est O (1), donc:

n opérations + (n - 1) opérations + (n - 2) opérations + ... + 2 opérations + 1 opération = somme (1 , n) opérations = (n * (n + 1))/2 = (n + n)/2 = O (n)

Answer 2

for(i=1;i<=(n-1);i++) { 
    for(j=(i+1);j<=n;j++) { 
     T=a[i,j]; 
     a[i,j]=a[j,i]; 
     a[j,i]=T; 
    } 
} 

La complexité du temps est O (n^2).