详解时间、空间复杂度(内含彩蛋~~)
2020-04-04 16:06:35来源:博客园 阅读 ()
详解时间、空间复杂度(内含彩蛋~~)
目录
- 一、时间复杂度:执行算法所需要的计算工作量
- (一)时间复杂度的理解
- 1.时间频度定义
- 2.(渐进)时间复杂度定义
- (二)时间复杂度的计算
- 计算攻略:
- 常见的算法时间复杂度由小到大排序:
- 大O表示法推导实例:
- 1.常数阶 ? O(1)
- 2.线性阶 ? O(n)
- 3.平方阶 ? O(n2)
- (一)时间复杂度的理解
- 二、 空间复杂度:执行这个算法所需要的内存空间
- 三、彩蛋
学习算法我们首先需要清楚的概念就是时间复杂度和空间复杂度
接下来我们就详细讲解一下时间复杂度和空间复杂度,为大家后面的学习打好基础!
算法入门书籍挑选点这里~ 帮你快速找到适合自己的算法书籍(详细,内含彩蛋哦~)
一、时间复杂度:执行算法所需要的计算工作量
(一)时间复杂度的理解
1.时间频度定义
我们需先明白:
一个 算法花费的时间 是与算法中语句的执行次数成正比的
(也就是说一个算法中语句执行次数越多,花费的时间也就越多)
时间频度:T(n): 一个算法中的语句执行次数,记为T(n)
2.(渐进)时间复杂度定义
T(n): 算法中基本操作重复执行的次数是问题规模n的某个函数。
f(n): 某个辅助函数
算法的(渐进)时间复杂度O(f(n)):
若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f (n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。
记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。
O(f(n)) 表示方法称为大O表示法
注意: T(n)不同,但时间复杂度可能相同。
(二)时间复杂度的计算
计算攻略:
- 用常数1代替运行时间中的所有加法常数。
(1) T(n)=n2+7n+6 ? T(n)=n2+7n+1 |
---|
- 修改后的运行次数函数中,只保留最高阶项。
(2)T(n)=n2+7n+1 ? T(n)=n2 |
---|
- 去除最高项系数
(3)T(n)=n2 ? O(n2 ) |
---|
注意:
(1)循环的时间复杂度 = 循环体的复杂度 × 该循环运行次数
(2)单纯的分支结构(不包括在循环结构中)其时间复杂度为O(1)
常见的算法时间复杂度由小到大排序:
常见的算法时间复杂度由小到大依次为: |
---|
O(1):常数阶 |
O(logan)【O(log2n)】:对数阶 |
O(n):线性阶 |
O(nlogan)【O(nlog2n)】:线性对数阶 |
O(n2):平方阶 |
O(n3):立方阶 |
O(nk):k次方阶 |
O(2n):指数阶 |
随着问题规模n的不断增大,上述时间复杂度越来越大大,算法的执行效率也越来越低 |
大O表示法推导实例:
1.常数阶 ? O(1)
int n =100;//执行1次
int sum =n*2;//执行1次
System.out println(sum);//执行1次
你可能会问代码一共执行了3次鸭,为什么时间复杂度不是O(3)呢?
这是因为用到了第一条攻略:用常数1代替运行时间中的所有加法常数。
本题中:T(n)=3根据第一条攻略:
(1) T(n)=3 ? T(n)=1 |
---|
(2) T(n)=1 ? O(1) |
2.线性阶 ? O(n)
int i= 0,sum=0;
for(i=0;i<n;i++){//for循环执行n次
sum=2*i;//执行一次for循环此语句执行一次
System.out.println(sum);//执行一次for循环此语句执行一次
}
所以:T(n)=2n
第三条攻略: 去除最高项系数
本例中根据第三条攻略可得:
(1) T(n)=2n ? T(n)=n |
---|
(2) T(n)=n ? O(n) |
3.平方阶 ? O(n2)
例1:
int i,j=0;
for(i=0;i<n;i++){//执行n次
for(j=0;j<n;j++){//执行n次
System.out.println(i + " " + j );
}
}
所以:T(n)=n2
T(n)=n 2 ? O(n2) |
---|
例2:
int i,j=0;
for(i=0;i<n;i++){//执行n次
for(j=i;j<n;j++){//注意j=i
System.out.println(i + " " + j );
}
}
当i=0,第二个for循环执行n次
当i=1,第二个for循环执行n-1次
当i=2,第二个for循环执行n-2次
当i=n-1,第二个for循环执行1次
执行总数T(n)=n+(n-1)+(n-2)+……1=+=(n 2+n)
根据第二条攻略、第三条攻略可得:
第二条攻略:修改后的运行次数函数中,只保留最高阶项。
第三条攻略: 去除最高项系数
T(n)=(n 2+n) ? T(n)=n 2 |
---|
T(n)=n 2 ? O(n2) |
二、 空间复杂度:执行这个算法所需要的内存空间
空间复杂度:
对一个算法在运行过程中临时占用存储空间大小的量度,记做S(n)=O(f(n))。
n为问题的规模,f(n)为算法所占存储空间的函数。
空间复杂度分类:
O(1)情况:
当算法的存储空间大小固定,与输入规模没有直接的关系时,空间复杂度记作O(1)。
O(n)情况:
当算法分配的空间和输入规模n成正比时,空间复杂度记作O(n)。
三、彩蛋
我将入门算法书中时间复杂度、空间复杂度讲解部分为大家截出来了,有需要的宝宝可以自取。
链接:https://pan.baidu.com/s/1mrMeuLv11Bf09zrE-DhFLA
提取码:yw8d
欢迎大家来公号 “小乔的编程内容分享站” 来找小乔玩~
一起学习Java基础+算法~
还有更多资源等你来拿哦~
原文链接:https://www.cnblogs.com/Qpgshare/p/12632688.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 数据源管理 | Kafka集群环境搭建,消息存储机制详解 2020-06-11
- Java--Stream流详解 2020-06-10
- B树和B+树的插入、删除图文详解 2020-06-09
- Spring Boot 2.3 新特性优雅停机详解 2020-06-08
- 详解SpringBoot(2.3)应用制作Docker镜像(官方方案) 2020-06-08
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash