文档章节

时间空间复杂度的解释

YKIT
 YKIT
发布于 2015/10/14 19:13
字数 472
阅读 72
收藏 8
点赞 0
评论 0

 

何为时间空间复杂度?

 

1》空间复杂度ON):

一个算法在运行过程中临时占用存储空间大小的量度。一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小,它包括为参数表中形参变量分配的存储空间和为在函数体中定义的局部变量分配的存储空间两个部分。

举例:

1)如一个算法的空间复杂度为一个常量,即不随被处理数据量n的大小而改变时,可表示为O(N)

2)当一个算法的空间复杂度与以2为底的n的对数成正比时,可表示为O(log2n)

3)当一个算法的空间复杂度与n成线性比例关系时,可表示为O(n)

4)递归函数的时间复杂度是O(N),因每次递归都需保存函数内部局部变量的存储空间。

 

2》时间复杂度

它定量描述了该算法的运行时间。算法的基本操作重复执行的次数是模块n的某一个函数f(n),因此,算法的时间复杂度记做:T(n)=O(f(n))。随着模块n的增大,算法执行的时间的增长率和 f(n) 的增长率成正比,所以 f(n) 越小,算法的时间复杂度越低,算法的效率越高。

 

常见的时间复杂度有:

常数阶O(1),对数阶O(log2n),线性阶O(n),

线性对数阶O(nlog2n),平方阶O(n^2),立方阶O(n^3),...

k次方阶O(n^k),指数阶O(2^n)。随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低。

 

 

 

 

© 著作权归作者所有

共有 人打赏支持
YKIT

YKIT

粉丝 14
博文 41
码字总数 8403
作品 3
苏州
后端工程师
时间复杂度和空房间复杂度

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

qq_38646470 ⋅ 2017/12/09 ⋅ 0

随笔:估算程序算法复杂度的理解

大体分为:事前估算(设计算法之前就估算此算法性能)和事后估算(运行后,通过收集数据) 直觉上以为是事后估算为主,毕竟,实践是检验真理的标准嘛。事后收集数据才是比较靠谱的。 不过,想法错...

wangtaotao ⋅ 2014/04/10 ⋅ 0

Google 面试题 | 矩形个数

专栏 | 九章算法 网址 | http://www.jiuzhang.com 题目描述 给一个二维数组构成的网格,其中的每一个格点非0即1。找出由4个不同格点上的1作为4个角,撑起的矩形个数。 注意: 1. 该矩形边与横...

九章算法 ⋅ 04/18 ⋅ 0

尾递归实现斐波那契数

一、先普及下尾递归:如果一个函数中所有递归形式的调用都出现在函数的末尾,我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时,这...

qq_38646470 ⋅ 2017/12/09 ⋅ 0

用户画像系统

用户画像分析是当前互联网产品对用户进行数据分析常用的一个手段,比如推荐场景,常见的算法是协同过滤算法,基于用户相似度和基于物品相似度,但是这两种算法适用的场景往往比较有限。 1.基...

满小茂 ⋅ 01/13 ⋅ 0

面试官:阮一峰版的快速排序完全是错的

面试官系列(番外): 别再使用阮一峰版的快速排序了 往期 面试官系列(1): 如何实现深克隆 面试官系列(2): Event Bus的实现 面试官系列(3): 前端路由的实现 面试官系列(4): 实现双向绑定Proxy比...

寻找海蓝96 ⋅ 05/11 ⋅ 0

LeetCode笔记:561. Array Partition I

问题(Easy): Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), ..., (an, bn) which makes sum of min(ai, bi) ......

Cloudox_ ⋅ 2017/12/26 ⋅ 0

玩转算法面试:(二)面试中的复杂度分析

面试中的时间复杂度分析 到底什么是大O n表示数据规模 O(f(n)) fn是关于n的一个函数。表示运行算法所需要执行的指令数,和f(n)成正比。 常见算法复杂度 和a.b.c.d这些常数项关系不大。主要还...

天涯明月笙 ⋅ 2017/09/20 ⋅ 0

算法的时间复杂度与空间复杂度分析

算法的时间性能分析 1.算法消耗的时间 一个算法的执行时间是指算法中所有语句执行时间的总和。每条语句的执行时间等于该条语句的执行次数乘以执行一次所需实际时间。 由于语句的执行要由源程...

xy294636185 ⋅ 05/25 ⋅ 0

java 时间复杂度和空间复杂度

同一问题可用不同算法解决,而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。 算法复杂度分为时间复杂度和空间复杂度。其作用: 时间复杂度是度...

浮躁的码农 ⋅ 2015/08/13 ⋅ 1

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Sqoop

1.Sqoop: 《=》 SQL to Hadoop 背景 1)场景:数据在RDBMS中,我们如何使用Hive或者Hadoop来进行数据分析呢? 1) RDBMS ==> Hadoop(广义) 2) Hadoop ==> RDBMS 2)原来可以通过MapReduce I...

GordonNemo ⋅ 7分钟前 ⋅ 0

全量构建和增量构建的区别

1.全量构建每次更新时都需要更新整个数据集,增量构建只对需要更新的时间范围进行更新,所以计算量会较小。 2.全量构建查询时不需要合并不同Segment,增量构建查询时需要合并不同Segment的结...

无精疯 ⋅ 17分钟前 ⋅ 0

如何将S/4HANA系统存储的图片文件用Java程序保存到本地

我在S/4HANA的事务码MM02里为Material维护图片文件作为附件: 通过如下简单的ABAP代码即可将图片文件的二进制内容读取出来: REPORT zgos_api.DATA ls_appl_object TYPE gos_s_obj.DA...

JerryWang_SAP ⋅ 35分钟前 ⋅ 0

云计算的选择悖论如何对待?

导读 人们都希望在工作和生活中有所选择。但心理学家的调查研究表明,在多种选项中进行选择并不一定会使人们更快乐,甚至不会产生更好的决策。心理学家Barry Schwartz称之为“选择悖论”。云...

问题终结者 ⋅ 43分钟前 ⋅ 0

637. Average of Levels in Binary Tree - LeetCode

Question 637. Average of Levels in Binary Tree Solution 思路:定义一个map,层数作为key,value保存每层的元素个数和所有元素的和,遍历这个树,把map里面填值,遍历结束后,再遍历这个map,把每...

yysue ⋅ 57分钟前 ⋅ 0

IDEA配置和使用

版本控制 svn IDEA版本控制工具不能使用 VCS-->Enable Version Control Integration File-->Settings-->Plugins 搜索Subversion,勾选SVN和Git插件 删除.idea文件夹重新生成项目 安装SVN客户......

bithup ⋅ 今天 ⋅ 0

PE格式第三讲扩展,VA,RVA,FA的概念

作者:IBinary 出处:http://www.cnblogs.com/iBinary/ 版权所有,欢迎保留原文链接进行转载:) 一丶VA概念 VA (virtual Address) 虚拟地址的意思 ,比如随便打开一个PE,找下它的虚拟地址 这边...

simpower ⋅ 今天 ⋅ 0

180623-SpringBoot之logback配置文件

SpringBoot配置logback 项目的日志配置属于比较常见的case了,之前接触和使用的都是Spring结合xml的方式,引入几个依赖,然后写个 logback.xml 配置文件即可,那么在SpringBoot中可以怎么做?...

小灰灰Blog ⋅ 今天 ⋅ 0

冒泡排序

原理:比较两个相邻的元素,将值大的元素交换至右端。 思路:依次比较相邻的两个数,将小数放在前面,大数放在后面。即在第一趟:首先比较第1个和第2个数,将小数放前,大数放后。然后比较第...

人觉非常君 ⋅ 今天 ⋅ 0

Vagrant setup

安装软件 brew cask install virtualboxbrew cask install vagrant 创建project mkdir -p mst/vmcd mst/vmvagrant init hashicorp/precise64vagrant up hashicorp/precise64是一个box......

遥借东风 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部