文档章节

时间复杂度

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
博文 27
码字总数 12994
作品 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

没有更多内容

加载失败,请刷新页面

加载更多

下一页

python3.6 取整除法

python3.6 中取整除法运算逻辑如下: d 非零,那么商 q 满足这样的关系: a = qd + r ,且0 ≤ r n1=7//3#7 = 3*2 +1n2=-6.1//3#-7 = 3*(-3)+2'{},{}'.format(n1,n2) 从运行结果可以...

colinux
22分钟前
3
0
阶段总结——用虚拟机搭建一个高可用负载均衡集群架构

[toc] linux基本知识已经介绍完,现有一个业务需要操作,通过对这个项目的操作,可以复习、总结、巩固之前的知识点; ** 用13台虚拟机搭建一个高可用负载均衡集群架构出来,并运行三个站点,...

feng-01
25分钟前
0
0
mysql 设置utf8字符集 (CentOS)

1.查看数据库及mysql应用目前使用的编码方式 (1)链接mysql 客户端 (2)执行:status 结果: 2.修改mysql 应用的字符编码(server characterset ) (1)打开配置文件:vim /etc/mysql/my...

qimh
26分钟前
0
0
windows无法格式化u盘解决方法

1。点开始-运行-输入cmd-format f: /fs: fat32 (这里f:是指U盘所在盘符) 这个格式化会很慢 请耐心等待

大灰狼wow
37分钟前
0
0
MySql 8.0连接失败

原来,MySql 8.0.11 换了新的身份验证插件(caching_sha2_password), 原来的身份验证插件为(mysql_native_password)。而客户端工具Navicat Premium12 中找不到新的身份验证插件(caching_s...

放飞E梦想O
54分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部