-1

此代码a[i,j]a[j,i]for交换的时间复杂度是多少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;
    }
}
4

2 回答 2

8

The inner loop does decreasing work from n to 1, and the actual work being done (swapping numbers) is O(1), so:

n operations + (n - 1) operations + (n - 2) operations + ... + 2 operations + 1 operation = sum(1, n) operations = (n * (n + 1)) / 2 = (n2 + n) / 2 = O(n2)

于 2010-08-23T08:04:01.083 回答
1
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; 
    } 
}

The time complexity is O(n^2).

于 2010-08-23T08:04:12.893 回答