什么是数据结构和算法？

先不考虑有关计算机的一切，我们思考一个问题：假设你所在的公司有员工上万人，如何编写一本能随身携带的通讯录？你可能首先需要搜集整理所有员工的个人信息，当然在此之前你得知道通讯录里面需要有哪些信息。我们假定需要以下员工个人信息：姓名、公司、部门、职务、手机号、电子邮箱、家庭地址，然后经过一番折腾，你终于把所有员工的这些信息搞到手了，你拥有的可能是部分电子表格、部分打印版的、部分手写的，电子表格同样的字段还有各种不同的格式，比如有的手机号是文本格式，有的又是数字格式等等。于是，你心里默默确认好各个字段的格式，然后新建了一张大表，把所有的电子表、非电子表信息全部整合到这一张表中。这时候我们需要考虑下一个问题，按什么顺序显示通讯录？你跟领导确认后得知需要先放公司领导，然后是各个职能部门及分公司，再是各个事业部及下面的子公司。你发现自己的信息表中压根就没考虑事业部，好吧，你可能需要在表中新插入一列 “事业部” 的字段。接下来呢？你还需要确认事业部下面公司的排序方式，每个公司部门的排序方式，每个部门员工的排序方式，你不能想当然地按照姓氏笔画或拼音，因为部门领导一般都要放在第一个然后是副职、主管这样一路下来，所以你还需要按职务大小排序。又经过一番折腾，你终于搞完了，在打印前你还需明确打印出来的小册子尺寸有多大，每个上面要显示多少位员工，然后才能在电子表中设置页面。你还可能需要考虑设置索引，至少到公司层面吧，如果贴心点你可能还会在公司分割线处做一些处理以便使用者可以快速翻到那一页。这看起来好像挺复杂的，但其实还有很多细节问题我们没有考虑，随便举几个例子：如果一个公司或部门正好只有个表头在某一页的最下方，要求这种直接把表头换到下一页；不同的字段要求不同的字体；字段内容太长的要求换行或缩小字体填充；所有人员信息以某个时间点为准，否则随时的人员进进出出会让你的通讯录永远无法完成；不同员工拿到的通讯录人员名单可能不同，你得根据权限设置。这些例子涉及到边界、格式、版本、权限等。噢，这还只是很普通的一个任务，实际中的任务（哪怕是做通讯录）都可能会比这更加复杂。

如果此时你还记得咱们讨论的主题，你可能已经有所感知了：没错，上面来自工作实际的简单任务中涉及到了大量的数据结构和算法细节。我们把整个流程简化后罗列一下：

• 确定你要的信息内容（数据结构）
• 收集、整合不同来源的数据并统一设置对应字段格式（数据结构）
• 不同层级的各种排序（算法）
• 设置索引（算法）

而事实上，该任务从头至尾的解决流程也可以看做是一个算法。在正式定义之前我们还可以做一件事：把刚刚的任务抽象。我们面临一个问题（或任务），而需要解决问题或完成任务就一定有相应的步骤和流程，每个步骤我们都需要有相应的方法处理，整个过程中我们在任何时候都可能需要一个地方来存储某种格式的数据，比如初始值、临时变量、结果等。现在，我们把这个抽象的结果局限在计算机中：数据结构就是数据对象在计算机中的组织方式。完成对数据结构各种操作所用的方法就是算法。联系刚刚的简化流程，比如我可以把所要的信息内容作为一个单元，单元中的每个项目都有不同的数据类型，而所有单元可以用数组存储；我们对数组进行排序，我们在数组中找到不同公司第一个人的下标作为该公司的索引。当然这只是众多 “联系” 中的一种而已。

我们之所以用这么一个看起来比较复杂的任务作为例子，除了因为它很真实外，更多的是我想通过这个例子让大家感知一下数据结构和算法怎么在实际工作中运用。数据结构和算法你都可以随心所欲按你的想法去设计，但前人已经有了大量优秀的最佳实践，这就是我们需要学习的。很多算法大多数的编程语言都进行了封装，让我们可以直接去调用，比如 python 的 sorted(array)，我们可能不用去管具体的细节，但像我们例子中的排序可能需要重新设计一下算法，如果你学习了算法大概不会写出 3-4 个或以上的 for 循环出来，因为你至少能够借鉴其思想。更广义的来说，Machine Learning，Deep Learning 这些也是算法，只是解决的问题和角度不同而已。

运行效率分析

既然有不同的数据结构和算法，那当然就有高下之分。也许对不同的业务场景来说，不同的数据结构和算法各有优劣，但假定就同一场景来说，还是有明显区分的。既然有区分，我们当然要选择最有效率的。什么是效率？我用三个字来概括：“好、快、省”，“好” 表示结果是对的，这也是最基本的要求；“快” 表示速度快；“省” 表示省空间，放在计算机中就是省内存。而我们一般假定不同算法的结果是一致的，就是首先假定所有的算法是对的，然后才讨论效率，所以正常情况下只讨论运行速度和内存占用。其实，这也是现代计算机的核心（CPU 和内存），毕竟依然没有突破冯 · 诺伊曼结构。

内存占用评估相对容易些，因为不管在哪台电脑上，1KB 信息占用的空间都是 1KB，属于绝对标准，不同的程序在不同机子上运行结果可以直接互相比较。但到了运行速度这里就比较麻烦了，同一个任务，你的程序在你电脑上运行了 1s，我的程序在我电脑上运行了 10s，这并不能说明你的程序比我的快，因为还有很多其他因素干扰，比如电脑配置、后台运行的其他进程、使用的编程语言、操作系统甚至任务本身（比如涉及网络请求，那网速也是个很关键的因素）。那应该怎么去评估两个完成同一任务的程序速度快慢呢？聪明的先辈们想到了一个办法：用执行时间的增长率！其中的基本思想是：随着问题规模的不断增加，执行时间的增长率差异主要体现在程序上。也就是说，当问题规模不断增加时，程序以外的因素可以不用考虑。举个例子来说，A 程序两层循环，B 代码一层循环，在问题规模足够大时，无论 B 代码在什么样的电脑或环境下运行，都会比 A 程序快。

但是，这种方法是抽象描述一个算法的性能，忽略了细节，只是在比较算法的时候作为通用的手段。当实现一个算法时，对细节的重视反映在关注常数倍差异。比如 O(1) 和 O(1000) 都是常数时间，但在现实中谁会愿意将自己的账单乘以 1000 呢？①

接下来我们就来看看如何来具体操作。在这里会用到三种标记符号：Θ，Ω 和 Ο，分别用来记录算法执行时间的真实情况，最好情况和最坏情况；又同时会被称为紧界、下界和上界。怎么理解呢？比如我们说给一个数组排序，或者在数组中查找一个元素，如果数组本来就是有序的，或者第一个元素就是要查找的元素，我们就在很短的时间内完成了任务，也就是该任务的最好情况；反过来当然就是最坏情况了。很显然，我们应该将更多的注意力放在一个算法最坏情况上，我们要分析这种最坏的情况耗时多少，以及这种情况出现的概率；换句话说，我们应该关注在平均情况下，最坏（长）的时间消耗是多少。

现在我们就看看如何用 O 来对此进行明确地标记。用查找元素来举例，假设我们需要在一个列表中找到需要找的元素，首先冒出来的想法大概就是一个一个去看，直到找到那个要的元素为止。刚刚已经提到过了，如果要找到的元素恰好是第一个，意味着我们只要（1）次操作就完成了任务；相反最坏的情况我们需要（n）次操作，其中 n 表示列表的长度。那么平均要多少次呢？当然就是 (1+2+…+n)/n=n/2*(1+n)/n = (1+n)/2 次，这就等于说如果我们需要 (1+n)/2 个单位的时间。那么，我们就把对该任务的这种操作方法的运行时间记为：O(n)，具体表示消耗的时间会随着 n 的增加而线性增加。需要注意的是，在算法分析中，O(n) 和 O(常数×n) 一般被认为执行时间的增长率是相等的（都是线性时间）。再来分析一下空间消耗，由于我们是一个一个对比，找到就返回，找不到就继续下一个，所以并不需要额外存储，因此空间复杂度被记为 O(1)，意味着该任务的空间不会随着 n 的扩大有任何的变化。

我们换个稍微复杂的排序问题：给定一组数将其按一定的顺序排列。首先想到的最简单的办法应该是依次选择最大的或最小的，一直到所有的数都排好为止。最好的情况是本来就排好了，这时候找是 O(1) 的复杂度，我们只需要将所有数过一遍就可以了，时间复杂度为 O(n)，也就是 Ω(n)；最坏的情况正好是反序的，此时我们需要：n + (n-1) + … + 1 = (1+n)×n/2 = (n + n×n)/2，它的最高项是 n 的平方，由于远超过线性时间，所以忽略比它低的项，时间复杂度记为：O(n²)，表明它的时间复杂度是平方级的。平均起来自然也是平方级的。至于空间复杂度，由于需要记住每次选择的最大（或最小）的值，因此需要 1 个单位的存储空间，又因为该空间是可覆盖的，所以空间复杂度为 O(1)。

我们再来一个更加复杂的例子。<待增补。>

那是不是要选择速度最快、空间最省的算法呢？在所有条件一样的前提条件下答案当然是 yes，但实际情况当然不是这样，所以还是需要根据具体的情况做出取舍。比如我们可以用字典把数组元素存起来，这样虽然空间复杂度变成了 O(n)，但查找的时间复杂度却是稳定的 O(1)，利用一点点内存稳定提高了查找速度，这在很多任务中是值得去做的。再比如对一组几乎有序的数据排序，我们可以依次将数据插入它们应该的位置（即，将比它大或小的全部移到它的右边，分别对应从小到大和从大到小排序），这样就会跳过已经排好的数据进而提高整体速度。所以，具体选择哪种算法要根据实际需求仔细分析后才能确定。

除了算法的选择外，数据结构的选择也非常类似。拿 C 语言举例，数组查找很快插入却很慢，链表却正好相反；如果我们的场景中查找非常频繁、插入很少，那可能会选择数组存储，比如菜单。此外，还有一些常见的数据结构比如树、图等，总之，不同的任务和场景可能需要不同的数据结构来配合。

参考文献

1. 算法技术手册 (豆瓣) 第一部分 第 2 章《算法的数学原理》：问题样本的规模和函数的增长率。