一本正经的聊数据结构（1）：时间复杂度

对于各位不想看文字的朋友，这个系列会配套视频， B 站视频地址：「一本正经的聊数据结构（1）：时间复杂度」

欢迎各位同学关注以及素质三连。

引言

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

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

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

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

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

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

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

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

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

时间复杂度

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

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

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

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

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

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

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

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

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

没错，就是服务器。

那么，什么是时间复杂度呢？

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

如果有其他的算我没说。

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

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

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

简单的介绍下冒泡排序：

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

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

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

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

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

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

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

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

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

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

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

我们可以在实际环境中直接测得的执行时间 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))