文档章节

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

翼动动空
 翼动动空
发布于 2016/05/09 09:32
字数 480
阅读 1469
收藏 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
从发明新的排序算法开始扯淡(四,挑战)

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

ueharaai
2012/09/28
0
1
前端 排序算法总结

前言 排序算法可能是你学编程第一个学习的算法,还记得冒泡吗? 当然,排序和查找两类算法是面试的热门选项。如果你是一个会写快排的程序猿,面试官在比较你和一个连快排都不会写的人的时候,...

zimo
2017/09/21
0
0
Java---插入类排序(直接插入排序,希尔排序)

Java—插入类排序(直接插入排序,希尔排序) Tags: 排序算法 直接插入排序 1.算法思想:其基本操作为将第i个记录插入到前面i-1个已经排好序的记录中 2.实现代码: 3.时间空间效率 (最好情况...

dorma_bin
2017/12/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

nginx的简单使用:负载均衡

nginx:反向代理的服务器;用户发送请求到nginx,nginx把请求发送给真正的服务器,等待服务器处理完数据并返回,再把数据发送给用户。 nginx作为一个反向代理服务器,能缓存我们项目的静态文...

osliang
33分钟前
2
0
网站title标题被改并被百度网址安全中心提醒的解决办法

国庆假日期间我们Sine安全接到众多网站站长求助网站标题被改导致在百度搜索中百度安全中心提醒被拦截,导致网站正常用户无法浏览网站被跳转到一些菠菜du博网站,而且很明显的一个特征就是在百...

网站安全
35分钟前
1
0
JDK版本与major.minor version的对照关系

其实,只需要记住jdk6对于major.minor version 50即可,其他版本自行计算即可。 ---------------------

码代码的小司机
37分钟前
1
0
C++基础教程面向对象学习笔记及心得感悟[图]

C++基础教程面向对象学习笔记及心得感悟[图] 使用友元函数重载算术运算符: C ++中一些最常用的运算符是算术运算符 - 即加号运算符(+),减运算符( - ),乘法运算符(*)和除法运算符(/...

原创小博客
46分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部