时间复杂度分析

2019-01-03

此文是学习《数据结构与算法之美》时的笔记。

为什么要分析复杂度

事后统计法

将代码跑一遍，通过统计、监控得到执行时间和占用空间，这种方法有很大的局限性。

1.1 测试结果非常依赖测试环境
最近有很多同学问我怎么选一款电脑，我首先会问什么需求(电脑用来干什么?是编程开发、还是后期制作、还是游戏或者是追剧？)。对于后期制作方面，选i7当然比i5好，i7的渲染能力是实测强于i5的。对于游戏，i7和i5性能发挥差不多，所以买i5处理器划算。当然还需要考虑散热以及预算等问题。。等等。对于编程测试环境的硬件不同会对测试结果有很大影响。

1.2 测试结果受数据规模的影响很大
对于同一种排序算法，待排序数据的有序度不一样，排序的执行时间就会有很大的差别。如果测试数据很小，测试结果可能无法真实的反应算法的性能。

大O复杂度表示法

/*求1，2，3，……，n的累加和*/
int add(int n)
{
    int sum = 0;
    int i = 1;
    for(; i<=n; i++)
    {
        sum = sum + i;
    }
    return sum;
}

假设每行代码执行时间一样为unit_time，T(n)为这段代码的执行时间。

T(n) = (2n+2)*unit_time

int fun(int n)
{
    int sum = 0;
    int i = 1;
    int j = 1;
    for(; i<=n; i++)
    {
        for(; j<=n; j++)
        {
            sum = sum + i*j;
        }
    }
    return sum;
}

上面这段代码的执行时间为：T(n) = (2n^2 + 2n +3)*unit_time

所有代码的执行时间T(n)与每行代码的执行次数n成正比

所有就有：T(n) = O(f(n))

大O时间复杂度实际上并不表示具体代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，也称为渐进时间复杂度。当n很大时，公式中的低阶、常量、系数并不左右增长趋势，所以可以忽略。

故，以上两个例子的时间复杂度记为：T(n)=O(n) T(n) = O(n^2)

时间复杂度分析原则

只关注循环次数最多的一段代码

大O只表示一种变化趋势，所以在分析一个算法、一段代码的时候，只关注循环执行次数最多的那一段就可以了。

int fun1(int n)
{
    int sum = 0;
    int i = 1;
    for( ; i<=n; i++)
    {
        sum = sum + i;
    }
    return sum;
}

fun1的总时间复杂度为O(n)

加法原则

总复杂度等于量级最大的那段代码的时间复杂度。

int fun2(int n)
{
    int sum1 = 0;
    int p = 1;
    for( ; p<100; p++)
    {
        sum1 = sum1 + p;
    }
    
    int sum2 = 0;
    int q = 1;
    for( ; q<n; q++)
    {
        sum2 = sum2 + q;
    }
    
    int sum3 = 0;
    int i = 1;
    int j = 1;
    for( ; i<=n; i++)
    {
        j = 1;
        for( ; j<=n; j++)
        {
            sum3 = sum3 + i*j;
        }
    }
    
    return sum1+sum2+sum3;
}

第一段执行了100次，和n的规模无关。

第二段代码时间复杂度为O(n)。

第三段代码时间复杂度为O(n^2)。

综合这三段代码的时间复杂度，取最大量级，所以这段代码的时间复杂度为O(n^2)。

乘法原则

嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。

int fun1(int n)
{
    int ret = 0;
    int i = 1;
    for( ; i<n; i++)
    {
        ret = ret + fun2(i);
    }
    return ret;
}

int fun2(int n)
{
    int sum = 0;
    int i = 1;
    for( ; i<n; i++)
    {
        sum = sum + i;
    }
    return sum;
}

这段代码的时间复杂度为：O(n^2)

常见的几种时间复杂度

指数阶：O(2^n) 和阶乘阶：O(n!)成为非多项式量级。

通常把时间复杂度为非多项式量级的算法问题成为NP问题(Non-Deterministic Polynomial，非确定多项式)。当数据规模n越来越大时，NP问题算法的执行时间会几句增加，非常低效。

O(1)

1
2
3

int i = 1;
int j = 2;
int sum = i + j;

O(logn)、O(nlogn)

/* 1 */
int i = 1;
while( i<=n )
{
    i = i*2;
}

/* 2 */
int i = 1;
while( i<=n )
{
    i = i*3;
}

1 代码的复杂度为log2(n)

2 代码的复杂度为log3(n)

对数是可以相互转换的:log3(n) = log3(2) * log2(n)所以:O(log3(n)) = O(C * log2(n))，其中C是一个常量，我们忽略系数C。

故将对数阶时间复杂度均表示为:log(n)

如果一段代码的时间复杂度为log(n)，执行了n遍，时间复杂度就为nlogn(n)。

O(m+n)、O(m*n)

int fun1(int m, int n)
{
    int sum1 = 0;
    int i = 1;
    for( ; i<m; i++)
    {
        sum1 = sum1 + i;
    }
    
    int sum2 = 0;
    int j = 1;
    for( ; j<n; j++)
    {
        sum2 = sum2 + j
    }
    
    return sum1+sum2;
}

这段代码的时间复杂度为：O(m+n)。

针对这种情况，时间复杂度和m、n均有关，加法原则就不正确了，乘法原则依然正确。

参考文章：《数据结构与算法之美》