给定代码的时间复杂度

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