文档章节

算法——时间复杂度和空间复杂度

翼动动空
 翼动动空
发布于 2016/05/09 09:32
字数 480
阅读 1472
收藏 1

一、时间复杂度 
T(n) = O(f(n)) 
随着问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称之为算法的渐进时间复杂度,即时间复杂度,其中f(n)是问题n的函数 
随着问题规模n的增大,T(n)增长最慢的算法为最优算法

时间复杂度T(n)的求法公式 
1、用常数1取代运行中的所有加法常数 
2、修改后,只保留最高阶项 
3、如果最高阶项存在且不是1,则去除与这个项相乘的常数

常见的时间复杂度: 

时间复杂度增长曲线 

时间复杂度比较 

O(1)  < O(lgn)  <  O(n) <  O(nlgn)  < O(n2)< O(n3)<O(2n)  < O(n!) < O(nn)

 

时间复杂度的两种情况: 
平均时间:算法运行的平均运行时间 
最坏运行时间:算法运行的最坏时间,在应用中最重要的要求,我们所提及的就是这种运行时间

二、空间复杂度 
一个算法在运行过程中临时占用存储空间大小的量度,记做S(n)=O(f(n))。比如直接插入排序的时间复杂度是O(n^2),空间复杂度是O(1)。而一般的递归算法就要有O(n)的空间复杂度了,因为每次递归都要存储返回信息。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。

某种意义上可以用空间换时间 
比如判断某年是否为闰年,可以使用算法判断。也可以事先定义1个数组,数组下标为年份,为闰年的值为1,反之为0。


 

© 著作权归作者所有

共有 人打赏支持
翼动动空
粉丝 15
博文 69
码字总数 36207
作品 0
成都
程序员
私信 提问
时间复杂度和空房间复杂度

一、时间复杂度:(注意:不是指程序运行时间) 1定义:一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/...

qq_38646470
2017/12/09
0
0
求二进制中1的个数(编程之美2.1)

行文脉络 解法一——除法 解法二——移位 解法三——高效移位 解法四——查表 扩展问题——异或后转化为该问题 对于一个字节(8bit)的变量,求其二进制“1”的个数。例如6(二进制0000 0110...

技术mix呢
2017/11/09
0
0
数据结构与算法——学习整理记录

===注:此文由本人结合网上资源整理总结而来,仅代表个人的学习与理解,如有错漏,欢迎指正!=== # 1. 数据结构 ## 1.1 数据结构是什么? 数据结构,直白地理解,就是研究数据的逻辑关系与存...

elinuxboy
2018/11/28
0
0
从发明新的排序算法开始扯淡(四,挑战)

前面讲的还没有涉及到排序算法的核心部分。即有没有办法改进合并算法呢? 合并两个排号序列需要额外的等长空间。如果不额外申请空间,就只能用O(n2)至O(nlogn)的方法代替。但是这个问题真的就...

ueharaai
2012/09/28
0
1
解读算法「时间」与「空间」复杂度——冰与火之歌

作者 | 程序员小吴 来源 | 五分钟学算法 算法(Algorithm)是指用来操作数据、解决程序问题的一组方法。对于同一个问题,使用不同的算法,也许最终得到的结果是一样的,比如排序就有前面的十...

AI科技大本营
2018/12/17
0
0

没有更多内容

加载失败,请刷新页面

加载更多

java 树形图构建

https://blog.csdn.net/massivestars/article/details/53911620/

kuchawyz
12分钟前
0
0
零基础如何学习大数据技术,大数据学习路线是什么?

在目前,当零基础学习大数据视频教程前,首先我们要学习Java语言和Linux操作系统,这两个是学习大数据的基础,学习的顺序不分前后。 对于小白学习大数据需要注意的点有很多,但无论如何,既然...

董黎明
14分钟前
0
0
123

123

lifes77
14分钟前
0
0
MySQL游标

MySQL游标 While循环 -- MySQL游标只能用于存储过程和函数-- 使用过程 声明、打开游标、使用游标、关闭游标-- 如果未明确关闭游标,END时会自动关闭-- https://dev.mysql.com/doc/refman/...

yysue
15分钟前
0
0
互联网下半场的角逐,玩转轻资产的大数据服务 | 阿里云栖开发者沙龙大数据专场(北京站)干货集锦

2019年1月18日下午,一个晴冷的冬日,由阿里巴巴MaxCompute开发者社区和阿里云栖社区联合主办的“阿里云栖开发者沙龙大数据技术专场”走近北京联合大学。当日,近200名大数据开发者和爱好者现...

阿里云官方博客
17分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部