给定代码的时间复杂度

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)。