文档章节

数据结构与算法系列之时间复杂度

AllenOR灵感
 AllenOR灵感
发布于 2017/09/10 01:17
字数 1632
阅读 3
收藏 0

前言

上一篇《数据结构和算法》中我介绍了数据结构的基本概念,也介绍了数据结构一般可以分为逻辑结构和物理结构。逻辑结构分为集合结构、线性结构、树形结构和图形结构。物理结构分为顺序存储结构和链式存储结构。并且也介绍了这些结构的特点。然后,又介绍了算法的概念和算法的5个基本特性,分别是输入、输出、有穷性、确定性和可行性。最后说阐述了一个好的算法需要遵守正确性、可读性、健壮性、时间效率高和存储量低。其实,实现效率和存储量就是时间复杂度和空间复杂度。本篇我们就围绕这两个"复杂度"展开说明。在真正的开发中,时间复杂度尤为重要,空间复杂度我们不做太多说明。

时间复杂度

时间复杂度和空间复杂度是算法效率的度量方法。也就是说,一个好的算法取决于它的时间复杂度和空间复杂度。
函数的渐近增长:给定两个函数f(n)和g(n),如果存在一个整数N,使得对于所有的n>N,f(n)总是比g(n)大。那么,我们说f(n)的增长渐近快于g(n)。

翻译过来就是:如果存在一个临界值,使得f(n)>g(n)永远成立,那么我们就认为"f(n)的增长渐近快于g(n)"。
这里我拿3个函数的增长曲线来说明问题。如下图:
函数一:X = 3n 注释:3乘以n
函数二:Y = 2n^2 注释:n的平方乘以2
函数三:Z = 2n^2 + 3n 注释:n的平方乘以2 + 3乘以n



当n=1时,Y < X < Z.
当n=2时,X < Y < Z.
所以,存在一个值,这个值位于1和2之间,使得X < Y < Z永远成立。我们就称Y的渐进增长快于X,Z的渐进增长快于Y,当然,根据传递性规则,Z的渐进增长也快于X。

定义

算法时间复杂度的定义:在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级。
算法的时间复杂度,也就是算法的时间量度,记作:T(n)= O(f(n))。
它表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐近时间复杂度,简称为时间复杂度。其中f(n)是问题规模n的某个函数。

时间复杂度计算方法

1.用常数1取代运行时间中的所有加法常数。
2.在修改后的运行次数函数中,只保留最高阶项。
3.如果最高阶项存在且不是1,则去除与这个项相乘的常数。
最后,得到的最后结果就是时间复杂度。

常见的时间复杂度

按数量级递增排列,常见的时间复杂度有:
常数阶O(1),对数阶O( log n ),线性阶O(n),线性对数阶O(nlog2n),平方阶O(n^2),立方阶O(n^3),...,k次方阶O(n^k),指数阶O(2^n)。随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低。
也就是:
常用的时间复杂度所耗费的时间从小到大依次是:O(1) < O(logn) < (n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)


时间复杂度顺序表.gif

常数阶

// 常数阶
int n = 0;
printf(“oneSong”);
printf(“oneSong”);
printf(“oneSong”);
printf(“oneSong”);
printf(“oneSong”);
printf(“oneSong”);
printf(“oneSong”);
printf(“oneSong”);
printf(“oneSong”);

上面这段代码的时间复杂度是O(1)。因为,按照时间复杂度的定义来说,n和问题的规模没有关系。当然,按照时间复杂度计算方法第一条也可以得出结果为O(1)。

线性阶

// 线性阶int i , 
n = 10086, sum = 0; 
for( i=0; i < n; i++ )
{ 
  sum = sum + i;
}

上面这段代码的时间复杂度是O(n),因为问题规模会随着n的增长而变得越来越大,并且这种增长是线性的。

平方阶

// 平方阶
int i, j, n = 998;
 for( i=0; i < n; i++ )
{ 
    for( j=0; j < n; j++ ) 
    {
       printf(“oneSong”); 
    }
}

上面这段代码外层执行n次,外层循环每执行一次,内层循环就执行n次,那总共程序想要从这两个循环出来,需要执行n*n次,也就是n的平方。所以这段代码的时间复杂度为O(n^2)。

对数阶

// 对数阶
int i = 1, n = 100;
 while( i < n )
{ 
i = i * 2;
}

由于每次i*2之后,就距离n更近一步,假设有x个2相乘后大于或等于n,则会退出循环。于是由2^x = n得到x = log(2)n,所以这个循环的时间复杂度为O(logn)。

算法的空间复杂度

算法的空间复杂度通过计算算法所需的存储空间实现,算法的空间复杂度的计算公式记作:S(n)=O(f(n)),其中,n为问题的规模,f(n)为语句关于n所占存储空间的函数。
在程序开发中,我们所指的复杂度不做特别说明的情况下,就是指时间复杂度。现在的硬件发展速度之快使得我们完全可以不用考虑算法所占的内存,通常都是用空间换取时间。加之算法的空间复杂度比较难算,所以,无论是在考试中还是在项目开发中,我们都侧重于时间复杂度。所以,空间复杂度,略过。

图片来源参考自:鱼C工作室。感谢鱼C工作室贡献出了这么好的图片。
如非特别说明,笔者所有文章都是原创文章。如果您喜欢这篇文章,转载请注明出处。如果您对数据结构感兴趣,请关注我,后续会更新大量精品文章供大家参考!
PS:本篇文章在博客园也有同步更新,大家也可以通过博客园关注我
http://www.cnblogs.com/wsnb

本文转载自:http://www.jianshu.com/p/688dd3c58a42

AllenOR灵感
粉丝 11
博文 2635
码字总数 83001
作品 0
程序员
私信 提问
《数据结构与算法之美》学习笔记之复杂度

本系列是极客时间中前 Google 工程师王争《数据结构与算法之美》专栏的学习笔记,想加强数据结构及算法能力的同学可以直接购买此专栏,跳转链接在此 复杂度分析是整个算法学习的精髓,只要掌...

骑摩托马斯
02/20
0
0
js算法初窥07(算法复杂度)

  算法复杂度是我们来衡量一个算法执行效率的一个度量标准,算法复杂度通常主要有时间复杂度和空间复杂度两种。时间复杂度就是指算法代码在运行最终得到我们想要的结果时所消耗的时间,而空...

zaking
2018/05/30
0
0
趣学算法系列-算法之美

趣学算法系列-算法之美 声明:本系列为趣学算法一书学习总结内容,在此推荐大家看这本算法书籍作为算法入门, 原作者博客链接,本书暂无免费电子版资源,请大家支持正版 书籍简介 本书内容按照...

wwlcsdn000
2017/11/21
0
0
「金三银四」| 手撕排序算法(JavaScript 实现)(上)

前言 俗话说金三银四 金九银十,马上又到了求职跳槽的黄金季。但是今年的这种大环境下,前端岗位的竞争势必比往日更加激烈。 在如今的面试过程中,算法是常常被考察的知识点,而排序作为算法...

_没有好名字了_
03/11
0
0
JavaScript 数据结构与算法之美 - 桶排序、计数排序、基数排序

1. 前言 算法为王。 想学好前端,先练好内功,只有内功深厚者,前端之路才会走得更远。 笔者写的 JavaScript 数据结构与算法之美 系列用的语言是 JavaScript ,旨在入门数据结构与算法和方便...

天明夜尽
07/29
0
0

没有更多内容

加载失败,请刷新页面

加载更多

SpringBoot中 集成 redisTemplate 对 Redis 的操作(二)

SpringBoot中 集成 redisTemplate 对 Redis 的操作(二) List 类型的操作 1、 向列表左侧添加数据 Long leftPush = redisTemplate.opsForList().leftPush("name", name); 2、 向列表右......

TcWong
今天
5
0
排序––快速排序(二)

根据排序––快速排序(一)的描述,现准备写一个快速排序的主体框架: 1、首先需要设置一个枢轴元素即setPivot(int i); 2、然后需要与枢轴元素进行比较即int comparePivot(int j); 3、最后...

FAT_mt
昨天
4
0
mysql概览

学习知识,首先要有一个总体的认识。以下为mysql概览 1-架构图 2-Detail csdn |简书 | 头条 | SegmentFault 思否 | 掘金 | 开源中国 |

程序员深夜写bug
昨天
10
0
golang微服务框架go-micro 入门笔记2.2 micro工具之微应用利器micro web

micro web micro 功能非常强大,本文将详细阐述micro web 命令行的功能 阅读本文前你可能需要进行如下知识储备 golang分布式微服务框架go-micro 入门笔记1:搭建go-micro环境, golang微服务框架...

非正式解决方案
昨天
8
0
前端——使用base64编码在页面嵌入图片

因为页面中插入一个图片都要写明图片的路径——相对路径或者绝对路径。而除了具体的网站图片的图片地址,如果是在自己电脑文件夹里的图片,当我们的HTML文件在别人电脑上打开的时候图片则由于...

被毒打的程序猿
昨天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部