文档章节

时间空间复杂度的解释

MPRO
 MPRO
发布于 2015/10/14 19:13
字数 472
阅读 74
收藏 8

 

何为时间空间复杂度?

 

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的不断增大,上述时间复杂度不断增大,算法的执行效率越低。

 

 

 

 

© 著作权归作者所有

共有 人打赏支持
上一篇: xshell 命令
MPRO

MPRO

粉丝 16
博文 48
码字总数 9778
作品 3
徐汇
后端工程师
私信 提问
随笔:估算程序算法复杂度的理解

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

wangtaotao
2014/04/10
0
0
时间复杂度和空房间复杂度

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

qq_38646470
2017/12/09
0
0
Google 面试题 | 矩形个数

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

九章算法
2018/04/18
0
0
尾递归实现斐波那契数

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

qq_38646470
2017/12/09
0
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
0

没有更多内容

加载失败,请刷新页面

加载更多

给windows server中的“未识别的网络”或“无法识别的网络”设置网络位置类型

在windows server中,如果网络没有被正确的识别,那么就需要手工设置一下网络位置类型。 将“公用网络”指定设置为“专用网络“ 【控制面板】--【系统和安全】--【管理工具】--【本地安全策略...

gugudu
47分钟前
1
0
阿里强制要求的21条Java开发规范,可以避免很多坑

1. 【强制】避免通过一个类的对象引用访问此类的静态变量或静态方法,无谓增加编译器解析成本,直接用类名来访问即可。 2. 【强制】所有的覆写方法,必须加@Override注解。 说明:getObject...

天王盖地虎626
今天
6
0
oracle dg 备库未设置convert参数导致ORA-01111,ORA-01110

查看trace 文件: MRP0: Background Managed Standby Recovery process started (amls) started logmerger process Sun Jan 20 07:55:53 2019 Managed Standby Recovery starting Real Time ......

hnairdb
今天
2
0
乱入Linux界的我是如何学习的

欢迎来到建哥学Linux,咳!咳!咳!开个玩笑哈,我是一个IT男,IT界的入门选手,正在学习Linux。 在之前,一直想进军IT界,学习IT技术,但是苦于没有人指导,也不知道学什么,最开始我自己在...

linux-tao
今天
2
0
乱入Linux界的我是如何学习的

欢迎来到建哥学Linux,咳!咳!咳!开个玩笑哈,我是一个IT男,IT界的入门选手,正在学习Linux。 在之前,一直想进军IT界,学习IT技术,但是苦于没有人指导,也不知道学什么,最开始我自己在...

linuxprobe16
今天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部