计算最佳、平均和最坏cae算法的复杂度。

Question

我有以下算法，我需要计算它的最佳情况、最坏情况和平均情况复杂性：

for (i=0; i<N; i++){
    for (j=0; j<N; j++){
        if  ((tab[i][j] % 2 != 0) && (tab[j][i] % 2 != 0)){
            tab[i][i] += tab [i][j] + tab[j][i];
        }
    }
}

问题是--如果是一个还是两个--因为里面有两个操作--还是只算对齐？我猜复杂性是n^2，但我不知道如何计算最佳情况、最坏情况和平均情况复杂度。

Answer 1

在每种情况下，复杂度都是N^2。实际操作数介于(c_N^2，C_N^2)之间，其中c，C是常量，c

Answer 2

复杂性是渐近的。因此，O(c*n)被视为O(n)，其中c是常数。如果要计算实际操作数，那么例如，在i循环中：

初始化I是一个操作。

I

i++增量操作发生N次。

因此，循环本身有2*N+2操作加上循环中的操作n次。