时间、空间复杂度分析

260 阅读5分钟

唐诗开篇,与文无关。

送杜少府之任蜀州

王勃(约650~约675年),古绛州龙门(山西盐津)人。与杨炯、卢照邻、骆宾王并成为“初唐四杰”,世称“王杨卢骆”,为四杰之首,被誉为“诗杰“。

城阙辅三秦,烽烟望无津。

与君离别意,同是宦游人。

海内存知己,天涯若比邻。

无为在歧路,儿女共沾巾。

为什么要分析复杂度?

代码跑一遍,通过统计、监控,就能得到算法执行的时间和n占用内存大小。为什么还要做时间、空间复杂度分析呢?

这种评估方法被称为事后统计法,其有很大的局限性。

1.结果非常依赖测试环境。

2.测试结果受数据规模影响较大。

所以就需要一种不需要依赖具体数据来测试就能粗略估算出算法执行效率的方法,这就是时间、空间复杂度分析方法

大O复杂度表示法

大O时间复杂度实际上并不表示具体代码的执行时间,而是表示代码执行时间随数据规模的变化趋势,所以,也叫做渐进时间复杂度(asymptotic time complexity),简称时间复杂度

时间复杂度分析

1. 只关注循环执行次数最多的一段代码

2.加法法则:总复杂度等于量级最大的那段代码的复杂度。

T1(n)=O(f(n)), T2(n)=O(g(n)); 那么T(n)=T1(n)+T2(n)=max(O(f(n)),O(g(n)))=O(max(f(n),g(n)))

T1(m)=O(f(m)), T2(n)=O(g(n)); 那么T(n)=T1(m)+T2(n)=O(f(m)+g(n))

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

T1(n)=O(f(n)), T2(n)=O(g(n)); 那么T(n)=T1(n)*T2(n)=O(f(n))*O(g(n))=O(f(n)*g(n))

T1(m)=O(f(m)), T2(n)=O(g(n)); 那么T(n)=T1(m)*T2(n)=O(f(m))*O(g(n))=O(f(m)*g(n))

几种常见时间复杂度

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

复杂度联想记忆

空间复杂度

全称渐进空间复杂度(asymptotic space complexity),表示算法的存储空间与数据规模之间的增长关系

最好、最坏、平均、均摊时间复杂度

最好情况时间复杂度(best case time complexity)

最坏情况时间复杂度(worst case time complexity)

平均情况时间复杂度(average case time complexity)

均摊时间复杂度(amortized time complexity)

最好、最坏情况时间复杂度

最好情况时间复杂度即在最理想情况下,执行代码的时间 复杂度。

最坏情况时间复杂度即在最糟糕情况下,执行代码的时间复杂度。

//n表示数组array的长度
int find(int[] array, int n, int x){
    int i = 0;
    int pos = -1;
    for(; i<n; ++i){
        if(array[i] == x) pos = i;
    }
    return pos;
}

上面这段代码是查找在数组(array)中变量x出现的位置,没有则返回-1。

按照时间复杂度小节中分析可知这段代码的时间复杂度是O(n),其中n代表数组的长度。

本例找到后可以直接跳出循环,下面是改进代码:

//n表示数组array的长度
int find(int[] array, int n, int x){
    int i = 0;
    int pos = -1;
    for(; i<n; ++i){
        if(array[i] == x) {
        pos = i;
        break;
        }
    }
    return pos;
}

那么此时这段代码的时间复杂度就不再是O(n)。

最好情况下数组中第一个元素就是要查找的变量x,后面的n-1个就无需再遍历,此时时间复杂度就是O(1)(最好时间复杂度)。 如果数组中不存在变量x,那么就需要遍历整个数组,此时时间复杂度就是O(n)(最坏时间复杂度)。

平均情况时间复杂度

最好最坏都是极端情况,发生概率并不大,平均时间复杂度能更好的反应平均情况下代码的复杂度情况。那么平均时间复杂度该怎么理解呢?

借助上个例子来解释。变量x可能出现在0~n-1或者不在数组中,者n+1种情况,各种情况相加在出n+1就是平均时间复杂度 (1+2+3+···+n+n)/(n+1)=n(n+3)/2(n+1),根据大O表示法其平均时间复杂度为O(n).

如果把各种情况出现的概率也考虑进来的话就是概率论中的加权平均值,也叫期望值。所以平均时间复杂度也是期望时间复杂度

均摊时间复杂度

借助实际例子来理解均摊时间复杂度。

//array表示一个长度为n的数组
//其中array.length 等于n
int[] array = new int[n];
int count = 0;
public void insert(int val){
    if(count == array.length) {
        int sum = 0;
        for(int i =0; i < array.length; ++i){
            sum = sum + array[i];
        }
        array[0] = sum;
        count = 1;
    }
    array[sount] = val;
    ++count;
}

实现功能是向数组中插入数据。当数组满了后遍历数组求和并将和赋值给数组第一个元素,然后将数据插入。如果数组一开始为空,则直接插入。

这段代码时间复杂度是多少呢?

不难分析,最好时间复杂度为O(1),最坏时间复杂度为O(n)。

那么平均时间复杂度是多少?同样根据概率论知识,假设每种情况出现概率一样, 1x1/(n+1) + 1x1/(n+1) + ··· + nx1/(n+1) = O(1)

首先对比一下find()和insert()差别:

find() 极端情况下为O(1)

insert() 大部分情况下都为O(1)

对于insert()这种情况就需要分析多次操作的平均来衡量其时间复杂度,

每一次O(n)的插入操作,都会跟着n-1次的O(1)插入操作,所以把耗时多的操作均摊到接下来的n-1次耗时少的操作上,均摊下来,这一组连续操作的均摊时间复杂度就是O(1)。均摊时间复杂度大致就是这个思想。(可能说的并不太明白)

均摊时间复杂度可以理解为一种特殊的平均时间复杂度

本篇总结的不够精炼,后期再进行修正。