文档章节

时间空间复杂度的解释

MPRO
 MPRO
发布于 2015/10/14 19:13
字数 472
阅读 73
收藏 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

粉丝 15
博文 43
码字总数 8410
作品 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. 该矩形边与横...

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

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

qq_38646470
2017/12/09
0
0
用户画像系统

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

满小茂
01/13
5
0

没有更多内容

加载失败,请刷新页面

加载更多

使用linux将64G的SDCARD格式化为FAT32

一、命令如下: sudo fdisk -lsudo mkfs.vfat /dev/sda -Isudo fdisk /dev/sda Welcome to fdisk (util-linux 2.29.2). Changes will remain in memory only, until you decide to wri......

mbzhong
22分钟前
3
0
深入理解Plasma(四):Plasma Cash

这一系列文章将围绕以太坊的二层扩容框架,介绍其基本运行原理,具体操作细节,安全性讨论以及未来研究方向等。本篇文章主要介绍在 Plasma 框架下的项目 Plasma Cash。 深入理解Plasma(1):...

HiBlock
昨天
1
0
命令参数的三大风格:Posix、BSD、GNU

今天读到命令行中参数的风格有三大类,即Unix/Posix、BSD、GNU。分别有以下特征: Unix/Posix风格,即命令后的参数,可以分组,便必须以连字符开头,如ps -aux。 BSD风格,即命令后的参数,可...

大别阿郎
昨天
2
0
PHP生成图片验证码

PHP生成图片验证码 /** * PHP生成图片验证码 * Class VerifyImage */class VerifyImage{ // 生成随机字串 private $verifyCode; // 图片对象 private $image; /**...

DrChenXX
昨天
1
0
纹理与表面细节添加方法---OpenGL纹理函数

OpenGL线纹理函数 OpenGL表面纹理函数 OpenGL体纹理函数 OpenGL纹理图案的颜色选项 OpenGL纹理映射选项 OpenGL纹理环绕 复制帧缓存中的OpenGL纹理图案 OpenGL纹理坐标数组 OpenGL纹理图案命名...

中国龙-扬科
昨天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部