c++ - 与えられたコードの時間計算量

Question

forと交換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) です。