1. 首页
  2. 数据结构

一本正经的聊数据结构(1):时间复杂度

一本正经的聊数据结构(1):时间复杂度

引言

最近有好多同学一直问我一些基础的问题,想了想,还是抄抄冷饭,聊聊基础。

一本正经的聊数据结构(1):时间复杂度

数据结构方面的内容,讲道理说实话,网上能找到的免费的资源大把,多到我一开始都不想写这个系列。

而且还有清华大学等顶级高校教授在网上录制的网课,这个就比较尴尬了,比专业我肯定是比不过人家教授讲的。

所以这个系列的名字起的就比较有意思了,叫「一本正经的聊数据结构」。

讲正经的讲不过,但是我可以讲不正经的啊。

一本正经的聊数据结构(1):时间复杂度

车开的有点远了,拐回来给想正经学习的同学推荐几本书,同时也是豆瓣上的数据结构评分最高的。

  1. 「清华大学计算机系列教材:数据结构(C++语言版)(第3版)」 这本书是邓俊辉教授编写的,同时配备了免费的视频,非常不错,对新人非常友好。

一本正经的聊数据结构(1):时间复杂度

  1. 「数据结构与算法分析」 这本书是一位美国教授写的,这本书的原书曾被评为20世纪顶尖的30部计算机著作之一,也是经典中的经典,就是有点厚。

一本正经的聊数据结构(1):时间复杂度

  1. 「算法导论」 这本书的范畴其实已经不是数据结构,而是算法了,但是数据结构和算法不分家嘛,我就也一起放在这里了,这本书同样也是经典中的经典,并且在美国被广泛的应用于本科生阶段,成为了本科生的教材的同时也成为了他们的噩梦。对于想买的同学我这里稍微泼点凉水,在买这本书之前最好先问问自己数学学得咋样,因为是讲算法,它的设计思想完全依托于背后的数学结构,它运作的机制以及它的美,也都来自它的数学。最好再问问自己的毅力如何,因为这本书非常的厚,特别适合用来垫显示器,别问我为啥,都是痛。

一本正经的聊数据结构(1):时间复杂度

时间复杂度

杂七杂八的讲完了,终于到正题了。

说道数据结构,第一个要提的概念就是时间复杂度和空间复杂度。

为什么我不谈空间复杂度呢?

因为简单,对的,就是这么耿直。

一本正经的聊数据结构(1):时间复杂度

说点靠谱的,因为现在存储空间不值钱了,现在不是 20 年前,想想那个年代的红白机,一个游戏 128K 大小,什么「魂斗罗」、「忍者必须死」、「坦克大战」,好像我又暴露童年了。

还有就是因为就渐进复杂度的意义而言,在任一算法的任何一次运行过程中所消耗的存储空间,都不会多于其间所执行基本操作的累计次数。整个算法所需的空间总量,也不过与基本操作的次数同阶。从这个意义上说,时间复杂度本身就是空间复杂度的一个天然的上限。

当然,对于输入的数据极其庞大的时候,由于时间复杂度确立的上限已经无法接受了,这种情况下,人们主要的做法是努力优化算法,比较常见的思路是空间换时间,背后的原因就是空间不值钱了。

顺便再歪一下,服务器的内存可能很多同学都没有概念。

emmmmmmmmmm,你们见过内存 256GB , 512GB , 1TB 的电脑么?

没错,就是服务器。

那么,什么是时间复杂度呢?

一本正经的聊数据结构(1):时间复杂度

这就要说到排序算法了,冒泡排序,学过程序的人接触的第一个算法一定是这个。

如果有其他的算我没说。

一本正经的聊数据结构(1):时间复杂度

为什么要选择排序算法呢?

因为用的多啊,平时我们接触的也很多,很多时候是你接触到了排序,但是你却没有意识到。

比如某点评、某团的外卖软件,你打开点外卖的时候,是不是会有什么综合排序,距离排序,评价排序之类的。或者说我们最常用的百度,使用某个关键字搜索后,是不是会按照某些规则将结果排序后展现在你的面前。

一本正经的聊数据结构(1):时间复杂度

简单的介绍下冒泡排序:

在由一组整数组成的序列 A[0, n – 1] 中,满足 A[i – 1] <= A[i] 的相邻元素称作顺序的;否则是逆序的。不难看出,有序序列中每一对相邻元素都是顺序的,亦即,对任意 1 <= i < n 都有 A[i – 1] <= A[i] ;反之,所有相邻元素均顺序的序列,也必然整体有序。

冒泡排序的核心是扫描交换,从前向后依次检查每一对相邻元素,一旦发现逆序即交换二者的位置。对于长度为n的序列,共需做 n – 1 次比较和不超过 n – 1 次交换,

我知道你们没看懂,下面给你们搞了个动图:

一本正经的聊数据结构(1):时间复杂度

时间复杂度是用来衡量一个算法的所需要的计算时间的,但是运行的时间是由多种因素综合而成的。

就拿排序来举例子,对于输入的数据量的不同,每个元素的次序的不同,每个元素数值大小的不同,都会对最终的排序时间造成影响。

比如你输入一串完全倒序的数字,如:{9, 8, 7, 6, 5, 4, 3, 2, 1},和一串仅有一位顺序不对,如:{1, 2, 3, 4, 5, 6, 7, 9, 8} ,这两串数字排序所需要的时间肯定是不同的。

还有数据量大小,实际上数据量大小是决定耗时的主要原因,一万个数字做排序和一亿个数字做排序,这其中所耗费的时间天差地别,实际上,在数据量大小比较接近的时候,相应的计算的耗时也越接近。

时间消耗的变化趋势可以表示为一个函数,这个函数称为这个算法的 时间复杂度

那么就有了这么一条定义:在规模为 n 的所有输入中选择执行时间最长者作为 T(n) , 并以 T(n) 度量该算法的时间复杂度。

这句话记住就完了,没啥原因,就是这么定义的。

小学数学课本上的定理啥时候跟你讲过原因,啥叫定理,定理的意思是就这么定义的。

一本正经的聊数据结构(1):时间复杂度

我们可以在实际环境中直接测得的执行时间 T(n) ,虽然可行是可行,但是作为评判不同算法性能优劣的标准,这个操作有点不切实际啊。

同一个算法,同样的输入数据,在不同的硬件平台上,或者不同的系统平台上,甚至是在不同的时间上,测试所消耗的时间都是不一样的,有不信邪的同学可以简单写一个循环进行累加计算,多循环几圈,比如先循环个 5000 次,计算一下消耗的纳秒数,甚至是毫秒数,多运行几次,看看能有多少次消耗的时间是一样的。

相信我,运行 10 次是可能得到 10 个不同的消耗的时间。

一种自然且可行的解决办法是,将时间复杂度理解为算法中各条指令的执行时间之和。在图灵机 (Turing Machine, TM) 和随机存储机 (Random Access Machine, RAM) 等计算模型中, 指令语句均可分解为若干次基本操作,比如算术运算、比较、分支、子程序调用与返回等;而在大多数实际的计算环境中,每一次这类基本操作都可在常数时间内完成。

如此,不妨将 T(n) 定义为算法所执行基本操作的总次数。也就是说, T(n) 决定于组成算法的所有语句各自的执行次数,以及其中所含基本操作的数目。
——来源:「数据结构」邓俊辉

我们来拆解一下刚才冒泡排序的时间复杂度,数学功底不好的同学这一段可以跳过,直接看后面的结果,这里我们先简单的写一个冒泡排序,我这里就用 Python 写了,有编程基础的同学应该都能看得懂:

def bubbleSort(nums):
    for i in range(len(nums)-1):
        for j in range(len(nums)-i-1):
            if nums[j] > nums[j+1]:
                nums[j], nums[j+1] = nums[j+1], nums[j]
    return nums

nums = [5,2,45,6,8,2,1]

print(bubbleSort(nums))

可以看到,在上面这一段代码中,冒泡排序是由两层循环套起来的,看循环,先找到最内层,从内层往外看。

在最内层,从前向后,依次比较各对相邻元素,如有必要则将其交换。那么在每一轮内循环中,需要扫描和比较 n – 1 对元素,至多需要交换 n – 1 对元素。元素的比较和交换,都属于基本操作,故每一轮内循环至多需要执行 2(n – 1) 次基本操作。

接着看外层,外层就比较简单了,直接是最多循环 n – 1 次。

那么,总共需要执行的基本操作不会超过 2(n - 1)^2 次。

表达式我们可以这么写:

T(n) = \sigma(2(n - 1)^2)

学过小学数学的我们可以对它做一个化简:

T(n) = \sigma(2(n - 1)^2) = \sigma(2n^2 - 4n + 2)

那么,到这里就结束了么?当然没有,因为时间复杂度我们关注的是数量级,在输入数据足够大的时候,函数的各项正的常系数可以忽略并等同于 1 ,那么我们最终的结果是:

T(n) = \sigma(n^2)

所以,我们最后得到的冒泡排序的时间复杂度是 \sigma(n^2) ,前面的看不懂没关系,这个结论背下来就好了。

一本正经的聊数据结构(1):时间复杂度

当然,我们上面得到的是一个算法的最坏情况下的时间复杂度,这种保守估计的方法并不排斥更好的情况出现,甚至如果直接得到的一个数列本身就已经排好序了,那么直接就会出现最好的时间复杂度。

相比较而言,「最坏情况时间复杂度」是人们最为关注且使用最多的,所以很多时候我们说时间复杂度就已经特指是最坏情况下的时间复杂度了。

本文就先到这里,感谢大家的关注与支持,如果能点个赞就再好不过了。

转载声明:本博客由极客挖掘机创作,采用 CC BY 3.0 CN 许可协议。可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在文末添加作者公众号二维码。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

评论列表(1条)

  • 海川 2020年6月3日 上午9:43

    好文!深入浅出!通俗易懂!

QR code