时间空间复杂度学习总结

点击蓝色“ 乔志勇笔记 ”关注我哟

加个“ 星标 ”,第一时间获取推送的文章哦!

一、代码的执行效率 :

快 : 时间复杂度

省: 空间复杂度

二、大O复杂度表示法

T(n)=O(f(n))

n: 数据规模的大小 // 需要重点理解 n 的含义

T(n): 所有代码的执行时间

f(n):每行代码执行的次数总和

O : 代码的执行时间T(n)与f(n)表达式成正比

三、时间复杂度分析

(1)定义:

渐进时间复杂度,算法的执行时间与数据规模之间的增长关系

(2) 分析方法

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

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

3、乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

(3)常见时间复杂度

1、多项式复杂度:

常量阶 O(1) 对数阶 O(logn)

线性阶 O(n) 线性对数阶O(nlogn)

平方阶O(n2) 立方阶 O(n3) k次方阶 O(nk)

2、非多项式复杂度:

指数阶 O(2n) 阶乘阶O(n!)

3、两个数据的规模来决定的复杂度:

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

四、空间复杂度

(1)定义

渐进空间复杂度,算法的储存空间与数据规模之间的增长关系

(2)常见空间复杂度

O(1)

O(n)

O(n2)

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

demo:

最好情况时间复杂度 O(1)

最坏情况时间复杂度 O(n)

六、平均情况时间复杂度

(1)定义

全称是加权平均时间复杂度 或者期望时间复杂度

(2)未考虑概率:

要查找的变量x在数组中的位置,有n+1种情况:在数组的 0 ~ n-1 位置中和不在数组中。

我们把每种情况下,查找需要遍历的元素个数累加起来,然后再除以n+1,就可以得到需要遍历的元素个数的平均值

(3)应该考虑概率:

加权平均时间复杂度 O(n)

七、均摊时间复杂度

(1)定义

对一个数据结构进行一组连续操作中,大部分情况下时间复杂度都很低,只有个别情况下时间复杂度比较高,而且这些操作之间存在前后连贯的时序关系,这个时候,我们就可以将这一组操作放在一块儿分析,看是否能将较高时间复杂度那次操作的耗时,平摊到其他那些时间复杂度比较低的操作上。而且,在能够应用均摊时间复杂度分析的场合,一般均摊时间复杂度就等于最好情况时间复杂度。

均摊时间复杂度就是一种特殊的平均时间复杂度

(2)示例

解析:

当i < len时, 即 i = 0,1,2,...,n-1的时候,for循环不走,所以这n次的时间复杂度都是O(1);

当i >= len时, 即 i = n的时候,for循环进行数组的copy,所以只有这1次的时间复杂度是O(n); 由此可知:

该算法的最好情况时间复杂度(best case time complexity)为O(1); 最坏情况时间复杂度(worst case time complexity)为O(n); 平均情况时间复杂度(average case time complexity), 第一种计算方式: (1+1+...+1+n)/(n+1) = 2n/(n+1) 【注: 式子中1+1+...+1中有n个1】,所以平均复杂度为O(1); 第二种计算方式(加权平均法,又称期望): 1 (1/n+1)+1 (1/n+1)+...+1 (1/n+1)+n (1/(n+1))=1,所以加权平均时间复杂度为O(1);

第三种计算方式(均摊时间复杂度): 前n个操作复杂度都是O(1),第n+1次操作的复杂度是O(n),所以把最后一次的复杂度分摊到前n次上,那么均摊下来每次 操作的复杂度为O(1)

八 练习题

特别注意 :len =10 ,并不是确定量,只是初始值而已

本例中数据规模的大小n 对应的含义还是 数组的长度

(1)解析:

1 、 最好情况时间复杂度为 O(1)

2 、最坏时间复杂度为 O(n)

最坏情况代码执行的次数跟每次数组的长度有关

第1次调用insert的执行的次数为 n ,

第2次调用insert的执行的次数为 2n ,

第3次调用insert的执行的次数为 2^2 * n

第k次调用insert的执行的次数为 2^(k-1) * n

最坏时间复杂度为 O(n)。

3 、平均时间复杂度O(1)

当每次遇到最坏情况时数组会进行2倍扩容,原数组被导入新数组,虽然数组的长度变大了,但是插入操作落在的区间的长度是一样的,分别是0~len-1, len~( 2len-1),....;

插入的情况仍是len+1种:0~len-1和插满之后的O(len);所以每次插入的概率是:p= 1/len+1, 最后求出加权平均时间复杂度为 1 p + 2 p+ ▪▪▪ + len*p + len * p = O(1) ;

4、均摊时间复杂度 O(1)

均摊复杂度由于每次O(len)的出现都跟着len次O(1),是前后连贯的,因而将O(len)平摊到前len次上,得出平摊复杂度是O(1)

摘抄自 :王争的数据结构与算法之美

近期文章:

5种分布式锁实现的对比?

Java并发编程学习体系

java8 Stream 史上最全总结

Java 网络编程"初探"

redis 知识点总结

java 核心技术学习总结 (一)

spring中"投机取巧"地限制 用户同时登陆

如果你喜欢本文

请长按二维码,关注 乔志勇笔记

我来评几句
登录后评论

已发表评论数()

相关站点

+订阅
热门文章