時間的給定的代碼複雜

Question

這是什麼代碼交換a[i,j]與a[j,i]爲j > i（轉置給定的矩陣）的時間複雜度：

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

內環確實減少從n個工作爲1，並且實際完成的工作（交換數字）爲O（1），因此：

n操作+（n-1）操作+（n-2）操作+ ... + 2操作+1操作= sum（1 ，n）操作=（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; 
    } 
} 

的時間複雜度是O（n^2）。