文档章节

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

翼动动空
 翼动动空
发布于 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
排序算法

排序算法 冒泡排序 选择排序 插入排序 快速排序(最常见) 希尔排序 归并排序 源码:Sorting 冒泡排序 冒泡排序(Bubble Sort)是一种简单的排序算法。它重复地遍历要排序的数列,一次比较两...

廖少少
2017/06/08
0
0
Java---插入类排序(直接插入排序,希尔排序)

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

dorma_bin
2017/12/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

配置Spring的注解支持

声明:本栏目所使用的素材都是凯哥学堂VIP学员所写,学员有权匿名,对文章有最终解释权;凯哥学堂旨在促进VIP学员互相学习的基础上公开笔记。 配置Spring的注解支持 以上也提到了使用注解来配...

凯哥学堂
32分钟前
0
0
关于Spring Aop存在的一点问题的思考

在本人前面的文章Spring Aop原理之切点表达式解析中讲解了Spring是如何解析切点表达式的,在分析源码的时候,出现了如下将要讲述的问题,我认为是不合理的,后来本人单纯使用aspectj进行试验...

爱宝贝丶
34分钟前
0
0
JavaScript 概述

JavaScript是面向Web的编程语言。绝大多数现代网站都使用了JavaScript,并且所有的现代Web浏览器——基于桌面系统、游戏机、平板电脑和智能手机的浏览器——均包含了JavaScript解释器。这使得...

Mr_ET
今天
0
0
Java Run-Time Data Areas(Java运行时数据区/内存分配)

Java运行时数据区(内存分配) 本文转载官网 更多相关内容可查看官网 中文翻译可参考 2.5. Run-Time Data Areas The Java Virtual Machine defines various run-time data areas that are use...

lichuangnk
今天
0
0
docker learn :services docker-compose.yml

docker-compose.yml定义了服务的运行参数 version: "3" services: web: # replace username/repo:tag with your name and image details image: hub.c.163.com/dog948453219/friendlyhello d......

writeademo
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部