文档章节

时间复杂度

liuyan_lc
 liuyan_lc
发布于 2018/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
博文 41
码字总数 19336
作品 0
济南
程序员
私信 提问
算法复杂度分析(下):最好、最坏、平均、均摊等时间复杂度概述

细化时间复杂度分析 代码千千万,有些代码逻辑会很复杂,所以为了更细化的分析算法的复杂度,再复杂度分析方面引入了4个知识点: 1.最好情况时间复杂度(best case time complexity)。 2.最...

Jonins
01/08
0
0
JavaScript 算法之复杂度分析

新的一年,先给大家整理分享一个简单而又重要的知识点:时间复杂度和空间复杂度。因为在前几篇文章中,提到了时间复杂度,也许有些小伙伴还不清楚。(ps:希望在我上篇文章留言的那位小伙伴别...

snowLu
01/03
0
0
JavaScript 算法之最好、最坏时间复杂度分析

上一篇文章中介绍了复杂度的分析,相信小伙伴们对常见代码的时间或者空间复杂度肯定能分析出来了。 思考测试 话不多说,出个题目考考大家,分析下面代码的时间复杂度(ps: 虽然说并不会这么写...

snowLu
01/07
0
0
时间复杂度跟空间复杂度

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

李雷岗
2016/11/30
8
0
算法优劣的评定标准(时间复杂度)

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

SVD
2016/05/05
104
2

没有更多内容

加载失败,请刷新页面

加载更多

Temp-Memo

Recommended Ref : SQL High CPU troubleshooting checklist -- Top 50 SQL highly consuming cpuSELECT TOP 50[Avg. MultiCore/CPU time(sec)] = qs.total_worker_time / 1000000 / qs......

Goopand
32分钟前
1
0
dotConnect for Oracle入门指南(七):存储过程

【下载dotConnect for Oracle最新版本】 dotConnect for Oracle(原名OraDirect.NET)建立在ADO.NET技术上,为基于Oracle数据库的应用程序提供完整的解决方案。它为设计应用程序结构带来了新的...

电池盒
34分钟前
2
0
如何使用阿里云ARMS轻松重现用户浏览器问题

客户投诉不断,本地却无法重现? 页面加载较慢是用户经常会反馈的问题,也是前端非常关注的问题之一。但定位、排查解决这类问题就通常会花费非常多的时间,主要原因如下: 页面是在用户端的浏...

阿里云官方博客
38分钟前
1
0
因资源用尽导致服务宕机

1. 事故的发生 服务调用场景和发生的事件如下图所示,红色表示服务不可用. 服务A和服务B都是内部服务,服务C_*为不同运营商提供的服务,遵循一样的协议。 某一天,突然发现所有服务A调用服务...

北风刮的不认真了
42分钟前
3
0
锤子科技"临死前"被"接盘" ,内部人士爆料已改签今日头条母公司

就在昨天,据据锤子科技内部人士透露,部分锤子科技员工在昨天已经接到了相关的临时通知,要求改签劳动合同至今日头条的母公司——字节跳动。至于这是锤子科技真正再度复活还是借尸还魂都不重...

终端研发部
51分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部