文档章节

时间空间复杂度的解释

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

精选30+云产品,助力企业轻松上云!>>>

 

何为时间空间复杂度?

 

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

粉丝 19
博文 50
码字总数 9836
作品 3
徐汇
后端工程师
私信 提问
加载中
请先登录后再评论。
时间复杂度和空间复杂度的理解

时间复杂度 时间复杂度指的是算法语句的执行次数,并不是运行时间。一个算法语句的执行次数最终都是可以通过函数f(n)来表示的 eg: 这里的x++就是算法语句,其f(n)=10-x f(n)=nn i++即算法语...

watchert
2019/08/28
22
0
随笔:估算程序算法复杂度的理解

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

wangtaotao
2014/04/10
0
0
恋上数据结构与算法(1-3)

不加密,高清,无水印 https://ke.qq.com/course/385223 腾讯课堂-小码哥教育-MJ恋上数据结构与算法-第一季-1666元 https://ke.qq.com/course/421398 腾讯课堂-小码哥教育-MJ恋上数据结构与算...

proteam123
06/12
0
0
leetcode151(翻转字符串里的单词)--Java语言实现

求: 给定一个字符串,逐个翻转字符串中的每个单词。 示例 1: 输入: "the sky is blue" 输出: "blue is sky the" 示例 2: 输入: " hello world! " 输出: "world! hello" 解释: 输入字符串可......

拓拔北海
昨天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

java常用开发支持类库

UUID类 UUID是一个生成无重复字符串的程序类(JDK1.5之后出现),这个程序类的主要功能是根据时间戳实现一个自动的无重复的字符串定义(无重复指的是出现重复的概率极低)。 一般在获取UUID时...

哼着我的小调调
3分钟前
0
0
亚马逊测评买家号多开_可以解决这个问题嘛?_微信公众号: VMlogin中文版

对于很多亚马逊卖家来说,做亚马逊测评是并不可少的,都在为了自己的店铺能够获得更多的销售,着重培养自己产品的各项属性,以求获得一个更好的权重排名从而获得更多的曝光,但是在旺季期间亚...

竹节猫-ASOer
10分钟前
0
0
从封装变化的角度看设计模式——对象创建

封装变化之对象创建 在对象创建的过程中,经常会出现的一个问题就是通过显示地指定一个类来创建对象,从而导致紧耦合。这是因为创建对象时指定类名将使你受特定实现的约束而不是特定接口的约...

良许Linux
11分钟前
0
0
Java基础系列——数组之java.util.Arrays使用以及可能出现的异常(12)

java.util.Arrays类即为操作数组的工具类,包含了用来操作数组(比 如排序和搜索)的各种方法。常用方法如下所示: boolean equals(int[] a,int[] b) 判断两个数组是否相等。 String toStrin...

卢佳鹏
24分钟前
19
0
Excel 2016如何删除带超链接表格前空格?

本文演示文档包含超链接。如图 先尝试使用trim和clean函数,=substitute(a1,char(9),"")公式。效果完全一致,超链接被删除。如下图 再次使用搜索引擎,网友给出建议,先提取超链接,删除空格...

白豆腐徐长卿
25分钟前
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部