一次搞懂时间复杂度和空间复杂度-LMLPHP

数据结构和算法因何而生?其实它们的存在就是为了解决“快”和“省”两个问题。也就是如何让代码运行的效率更快!让代码的执行更节省存储空间!而时间复杂度和空间复杂度就是来衡量我们的代码是否快!是否省!掌握了这两种分析技能我们就能炼成火眼金睛!一眼瞄出“快”和“省”的代码!

时间复杂度

来咱们先看一段代码

一次搞懂时间复杂度和空间复杂度-LMLPHP

虽然每行代码具体的执行时间是不一样的,但是我们就粗略的认为每一行代码执行的速度都为t,那这情况就是第二行t+第三行n*t+第四行n*t+第六行t。

所以这段代码的总执行时间就是2t+2n*t。我们可以看到这段代码执行的总时间和每行代码执行的次数n成正比!

则可提取出一个公式T(n)=O(f(n))。从我们的例子来看就是T(n)=O(2n+2),而当n很大的时候,公式种的常量系数和低阶部分都不会影响整体的增长情况,所以可以忽略了。

因此可以记为T(n)=O(n) 这就是我们的大0时间复杂度表示法了!

大O时间复杂度实际也叫渐进时间复杂度(asymptotic time complexity),简称时间复杂度。

它实际上表明的只是代码的执行时间随数据规模增长的变化趋势,而不是代码执行的具体时间。

咱再来看一段代码,我把每行的执行时间直接标注在代码后面

一次搞懂时间复杂度和空间复杂度-LMLPHP

按照咱们上面说的提取出的大致总执行时间4t+2n*t+2n²*t =>t(2n+2n²+4)得到T(n) = O(2n+2n²+4)。

又因为可以忽略常量系数和低阶部分,所以最终记为T(n)=O(n²)。

所以我们只需要关注循环次数最多的那一行代码!它的执行次数就代表我们的时间复杂度

其实虽然代码有五花八门,但是常见的时间复杂度也就几种:

一次搞懂时间复杂度和空间复杂度-LMLPHP

前面已经举过O(n) 和O(n²),我们再讲讲O(1)和O(logn)

1. O(1)

1 int a = 1;
2 int b = 1;

上面这段代码,它的时间复杂度就是O(1),注意不是O(2),也就是只要代码的执行实际不随着n的增长而增长,也就是基本上方法内没有循环递归这样的语句,即使你一个方法有几千行代码,时间复杂度就是O(1)。

2. O(logn)

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

对数阶的时间复杂度啊,相对而言是最难分析的。不过问题不大让我们来深入理解一下!

咱们看看上面的变量i,它的初始值是1,每次循环之后就乘2,这就完全符合我们学过的等比数列:

初始值是1 那就是2º ,然后 2¹ , 2² ......最终2的x次方等于n而这个x其实就是我们运行的次数,你看看是这样的吧。所以x=log2ⁿ,时间复杂度就是O(log2ⁿ)!

那我们循环不乘2,咱们乘3那时间复杂度是不是就是O(log3ⁿ)?

实际上,咱们不过底数是多少,我们对于对数阶的时间复杂度都记为O(logn),因为对数之间是可以互相转换的log3ⁿ=log3² * log2ⁿ,提取出常数之后O(log3ⁿ) = O(常量*log2ⁿ)

所以我们统一记为O(logn)!

再更细一点,时间复杂度还分:最好情况时间复杂度、最坏情况时间复杂度,平均情况时间复杂度,均摊时间复杂度。

来上代码!

一次搞懂时间复杂度和空间复杂度-LMLPHP

最好的情况就是查的这个x在数组的第一个位置!所以最好情况时间复杂度就是O(1)。

最坏的情况就是查的这个x在数组的最后一个位置或者没查到!这两种情况都遍历了整个数组,所以最坏情况时间复杂度就是O(n);

但是这两种都太极端了,我们来平均一下,简单点假设x在这个数组里面的概率为1/2,那不在这里面的概率也是1/2,如果在数组里的话,在0到(n-1)之间每个位置的概率就是1/2n。所以我们可以推导出公式:

一次搞懂时间复杂度和空间复杂度-LMLPHP

在按照我们之前说的省略一下常数,平均情况时间复杂度就是O(n)。

一次搞懂时间复杂度和空间复杂度-LMLPHP

一般情况下,正常的时间复杂度就已经够我们用的了!除非在这三种情况下,时间复杂度有量级的变化,我们才会以这三种情况来区分!

咱再来了解一下更高级的玩意!均摊时间复杂度,这东西比我们上面说的那三种用到的更少了。

听起来好像和平均情况时间复杂度有点像,但是不太一样。就比如ArrayList,我们知道ArrayList底层是数组实现了,数组是有固定大小的设为n,正常情况下我们的插入数据的时间复杂度是O(1) 。

一次搞懂时间复杂度和空间复杂度-LMLPHP

如果我们自己实现了一个ArrayList,在扩容时没有调用System.arraycopy(),而且自己new一个新的数组,大小为之前的2倍,并且用for来拷贝的话

(不推荐,效率比System.arraycopy()低,只是为了说明均摊时间复杂度!)。

所以扩容的时候我们需要搬迁以前的n个数据的到新的数组上,这一次操作的时间复杂度就是O(n)。

然后之后一段时间内我们插入的时间复杂度又是O(1)。就只要往复又到扩容然后正常插入。。。。。循环。

我们总结下这种规律,在O(n)插入之后都伴随着n次的O(1)插入,那我们把n平均的分到每次O(1)插入上,那均摊下来是不是几乎所有的插入的时间复杂度都是O(1)了呢?这就是均摊时间复杂度,一般的均摊时间复杂度都等于最好情况时间复杂度!

空间复杂度

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

同样咱们先看一段代码

1 int i= 1;
2 int[] a = new int[n];

其实和时间复杂度分析是一样的,第一行代码申请了一个存储变量i,第二行申请了n个大小的int类型数组,因为第一行是常量,所以忽略,只看第二行,所以得出空间复杂度就是O(n)。

而且常见的空间复杂就是O(1), O(n), O(n²),想对数阶的都很少遇到,而且具体分析的也比时间复杂度简单多啦!

总结

理解了这两种复杂度分析等于我们掌握了代码中的“时间”和“空间”能力!有点厉害哈哈哈。


本文分享自微信公众号 - yes的练级攻略(yes_java)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

09-11 01:28