算法复杂度

1 复杂度定义

空间复杂度S(n)—— 程序在执行时占用存储单元的长度。通常和输入数据的规模有关。S(n)过高可能导致内存超限，造成程序非正常中断。

时间复杂度 T(n) —— 程序在执行时耗费时间的长度。通常和输入数据的规模有关。

2 复杂度分析

下图所示为不同复杂度随着n的逐渐增大所耗费的时间复杂度。

Fig1 不同时间复杂度曲线

Fig1的复杂度分析如下：

• 在算法设计时，我们应当尽可能使得复杂度最小。
• 当算法复杂度为O(log n^2)时，应想办法变为O(n log n)。
• 最高效的是O(log n)。

Notices:

• 两段代码相加的复杂度为分别求复杂度，取两者中的较大者。
• 两段代码乘积的复杂度为分别求复杂度，取两者的乘积。
• for循环的时间复杂度为循环次数乘以循环体代码的复杂度。
• if-else复杂度，取分支条件中的较大者。

3 应用实例

最大子列和问题。

• 方法1：双重循环，算法的时间复杂度为O(N*N)。

int MaxSubseqSum2( int A[], int N )
{ int ThisSum, MaxSum = 0;
    int i, j;
    for( i = 0; i < N; i++ ) { /* i是子列左端位置 */
        ThisSum = 0; /* ThisSum是从A[i]到A[j]的子列和 */
        for( j = i; j < N; j++ ) { /* j是子列右端位置 */
            ThisSum += A[j];
            if( ThisSum > MaxSum ) /* 如果刚得到的这个子列和更大 */
                MaxSum = ThisSum;  /* 则更新结果 */
        }
    } 
    return MaxSum;
}
           

• 方法2：在线处理，算法的时间复杂度为O(N)。

int MaxSubseqSum4( int A[], int N )
{ int ThisSum, MaxSum;
    int i;
    ThisSum = MaxSum = 0;
    for( i = 0; i < N; i++ ) {
        ThisSum += A[i];   /* 向右累加 */
        if( ThisSum > MaxSum )
            MaxSum = ThisSum;    /* 发现更大和则更新当前结果 */
        else if( ThisSum < 0 )   /* 如果当前子列和为负 */
            ThisSum = 0;  /* 则不可能使后面的部分和增大，抛弃之 */
    }
    return MaxSum
}