文档章节

时间复杂度

liuyan_lc
 liuyan_lc
发布于 07/23 15:41
字数 467
阅读 6
收藏 0

1. 维基上的定义

在计算机科学中,算法的时间复杂度是一个函数,它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,亦即考察输入值大小趋近无穷时的情况。


2 复杂度分类

  1. 最坏情况复杂度:(常说的复杂度)定义为任何大小的输入 n 所需的最大执行时间
  2. 平均情况复杂度:通常有特别指定才会使用

3. 算法归类

  1. 线性时间算法:T(n) = O(n);
  2. 指数时间算法:T(n) = O(Mn) 和 Mn= O(T(n)) ,其中 M ≥ n > 1;

4. 常见时间复杂度列表

名称运行时间 T(n)算法举例
常数时间O(1)判断一个二进制数的奇偶
对数时间O(log n)二分搜索
线性时间O(n)无序数组的搜索
线性对数时间O(nlog n)最快的比较排序
二次时间O(n^2)冒泡排序、插入排序

常见的算法时间复杂度由小到大依次为:Ο(1)<Ο(logn)<Ο(n)<Ο(nlogn)<Ο(n2)<Ο(n3)<…<Ο(2n)<Ο(n!) 注:尽可能选用多项式阶O(nk)的算法(即P问题)


5 通俗理解

  1. 知乎-司马懿的回答

© 著作权归作者所有

共有 人打赏支持
liuyan_lc
粉丝 0
博文 32
码字总数 14476
作品 0
济南
程序员
算法的时间复杂度与空间复杂度分析

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

xy294636185
05/25
0
0
时间复杂度跟空间复杂度

时间复杂度:执行一个算法所需要的时间的衡量标准。 空间复杂度:执行一个算法所需要的空间的衡量标准。 拿时间换空间和拿空间换时间是优化算法的途径。 求时间复杂度: 如果算法的执行时间不...

李雷岗
2016/11/30
8
0
算法基础-时间复杂度和空间复杂度(转载)

转自:http://blog.csdn.net/booirror/article/details/7707551 算法的时间复杂度和空间复杂度合称为算法的复杂度。 1.时间复杂度 (1)时间频度 一个算法执行所耗费的时间,从理论上是不能算...

banyoukang
2016/03/30
29
0
时间复杂度和空间复杂度详解

算法的时间复杂度和空间复杂度合称为算法的复杂度。 1.时间复杂度 (1)时间频度 一 个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对...

cccyb
2016/10/08
14
0
算法优劣的评定标准(时间复杂度)

同一问题可用不同算法解决(比如同是创建一个有向图CreateGraph(G,v),选择邻接矩阵时间复杂度是O(n*n+n+e),而邻接表是O(n+e)) ,而一个算法的质量优劣将影响到算法乃至程序的效率。算...

SVD
2016/05/05
104
2

没有更多内容

加载失败,请刷新页面

加载更多

如何在Java中生成比特币钱包地址

让我们通过学习比特币(Bitcoin)如何实施该技术的各个方面来工作,好吗?该技术包括以下几个方面: 比特币地址bitcoin address是用来发送和接收比特币的。 交易transaction是比特币从一个地...

geek12345
21分钟前
3
0
面试必备Linux基础知识

学习Linux之前,我们先来简单的认识一下操作系统。 一 从认识操作系统开始 1.1 操作系统简介 我通过以下四点介绍什么操作系统: 操作系统(Operation System,简称OS)是管理计算机硬件与软件...

小小明童鞋
22分钟前
6
0
SpringBoot基础教程3-1-3 Quartz定时任务单点持久化

1 概述 实际项目中,复杂的定时任务都会结合持久化,动态改变定时任务状态,本文将介绍基于Quartz的定时任务单点持久化方式,通过RESTful风格,演示定时任务的CRUD,最后使用Swagger测试。 ...

Mkeeper
38分钟前
11
0
Android入门—文件目录解析

AndroidManifest.xml 是每个android程序中必须的文件,它位于整个项目的根目录。我们每天都在使用这个文件,往里面配置程序运行所必要的组件,权限,以及一些相关信息。但是对于这个文件,我...

haoyuehong
41分钟前
8
0
IDEA中Maven打包时如何跳过测试

方法1:直接使用IDEA提供的方式 Maven命令栏的工具栏有下图中的图标,上面就写着 Skip Tests 按下图标后,如下图,test就不可用了 直接使用package命令即可。 方法2:自己编辑maven命令 进入...

karma123
55分钟前
11
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部