|
本文将从编程的角度出发，重新梳理这些内容，作为第一篇“基础思想”的总结。 5.1 数据结构、编程语言和基础算法这一节我们汇总数学在常见的数据结构、编程语言和基础算法中的体现，让你对数学和编程的关系有个新的认识。 5.1.1 数据结构先来看一些基本的数据结构，你可别小看这些数据结构，它们其实就是一个个解决问题的“模型”。有了这些模型，你就能将一个个具体的问题抽象化，然后再来解决。这里从最简单的数据结构数组开始介绍。自从你开始接触计算机编程，数组一定是你经常使用的数据结构，它的特点也很鲜明。数组可以通过下标直接定位到所需的数据，因此数组特别适合快速地随机访问。它常常和循环语句相结合来实现迭代法，例如二分搜索、斐波那契数列等。另外，将要在第三篇“线性代数”介绍的矩阵也可以使用多维数组来表示。不过，数组只对稠密的数列更有效。如果数列非常稀疏，那么很多数组的元素就是无效值，浪费了存储空间。此外，数组中元素的插入和删除也比较麻烦，需要进行数据的批量移动。 那么对稀疏的数列而言，使用什么样的数据结构更有效呢？答案是链表。链表中的结点存储了数据，而链表结点之间的相连关系，在C和C++语言中是通过指针来实现的，而在Python和Java语言中是通过对象引用来实现的。链表的特点是不能通过下标来直接访问数据，而必须按照存储的结构逐个读取。这样做的优势在于，不必事先规定数据的数量，也不再需要保存无效的值，因而表示稀疏的数列时可以更有效地利用存储空间，同时也利于数据的动态插入和删除。但是，相对于数组，链表无法支持快速地随机访问，所以进行读写操作时就更耗时。和数组一样，链表也可以是多维的。对于非常稀疏的矩阵，也可以用多维链表的结构来表达。此外，在链表结构中，点和点之间的连接，分别体现了图论中的顶点和边。因此，我们还可以使用指针、对象引用等来表示图结构中的顶点和边。常见的图模型，例如多叉树、无向图和有向图等，都可以用指针或引用来实现。 在数组和链表这些基础的数据结构之上，我们可以构建更复杂的数据结构，如哈希表、队列和栈等。这些数据结构，提供了逻辑更复杂的模型，可以通过数组、链表或这两者的结合来实现。在第1章中，我提到过哈希的概念，而哈希表就可以通过数组和链表来构造。在很多编程语言中，哈希表的实现采用的就是链式哈希表。这种方法的主要思想是，先分配一个很大的数组空间，而数组中的每一个元素都是一个链表的头部。随后，我们就可以根据哈希函数算出的哈希值（也叫哈希的key）找到数组中的某个元素及其对应的链表，然后将数据添加到这个链表中。之所以要这样设计，是因为存在哈希冲突。对于不同的数据，哈希函数可能产生相同的哈希值，这就是哈希冲突。如果数组的每个元素都只能存放一个数据，那就无法解决冲突。如果每个元素对应了一个链表，那么当发生冲突的时候，我们就可以将多个数据添加到同一个链表中。可是，将多个数据存放在一个链表中就代表访问效率不高。所以，我们要尽量找到一个合理的哈希函数，减少冲突发生的机会，提升检索的效率。第1章中还提到了使用求余相关的操作来实现哈希函数。我在这里举个例子，如图5-1所示。  图5-1 基于数组和链表实现的哈希结构，解决了哈希冲突 我们将对100求余作为哈希函数。因此数组的长度是100。对于每一个数据，通过它对100求余，确定它在数组中的位置。如果多个数据的求余结果一样，就产生冲突，使用链表来解决。可以看到，图5-1中键为98的链表没有冲突，而0、1、2、3和99的链表都有冲突。 介绍了哈希，再来看看栈这种数据结构。我在介绍树的深度优先搜索时讲到过栈。它是先进后出的。在进行函数递归的时候，函数调用和返回的顺序也是先进后出，所以，栈体现了递归的思想，可以实现基于递归的编程。实际上，计算机系统里的函数递归，在内部也是通过栈来实现的。虽然直接通过栈来实现递归不如函数递归调用那么直观，但是，由于栈可以避免使用过多的中间变量，它可以节省内存空间。 在介绍广度优先搜索策略时，我谈到了队列。队列和栈最大的不同在于，它是一种先进先出的数据结构，先进入队列的元素会优先得到处理。队列模拟了日常生活中人们排队的现象，其思想已经延伸到很多大型的数据系统中，例如消息队列。在消息系统中，生产者会源源不断地推送新的消息，而消费者会对这些消息进行处理。可是，有时消费者的处理速度会慢于生产者推送的速度，这会带来很多复杂的后续问题，因此可以通过队列实现消息的缓冲。新产生的数据会先进入队列，直到消费者处理它。经过这样的异步处理，消息队列实现了生产者和消费者的松耦合，对消费者起到了保护作用，使它不容易被数据洪流冲垮。相比于哈希表，队列和栈更为复杂的数据结构是基于图论中的各种模型，例如各种二叉树、多叉树、有向图和无向图等。通常，这些模型表示了顶点和顶点之间的稀疏关系，所以它们常常是基于指针或者对象引用来实现的。我在讲前缀树、社交关系图和交通导航的案例中，都使用了这些模型。另外，树模型中的多叉树、特别是二叉树体现了递归的思想。之前的递归方式编程的案例中的图示也可以对应到多叉树的表示。 5.1.2 编程语句在学习编程的时候，我们都接触过条件语句、循环语句和函数调用这些基本的语句。条件语句的一个关键元素是布尔表达式。它其实体现了逻辑代数中逻辑和集合的概念。第1章介绍过逻辑代数，它也被称为布尔代数，主要包括逻辑表达式及其相关的逻辑运算，可以帮助我们消除自然语言所带来的歧义，并严格、准确地描述事物。在编程语言中，我们将逻辑表达式和控制语言结合起来，例如Java语言的if语句： if(表达式) {函数体1} else {函数体2}：若表达式为真，执行函数体1，否则执行函数体2 当然，逻辑代数在计算机中的应用远不止条件语句，例如SQL语言中的Select语句和布尔检索模型。Select是SQL查询语言中十分常用的语句。这个语句将根据指定的逻辑表达式，在一个数据库中进行查询并返回结果，而返回的结果就是满足条件的记录之集合。类似地，布尔检索模型利用逻辑表达式，确定哪些文档满足检索的条件并将它们作为结果返回。除了条件语句中的布尔表达式，逻辑代数还体现在编程中的其他地方。例如，SQL语言中的Join操作。Join有多种类型，每种类型其实都对应了一种集合的操作。 循环语句可以让我们进行有规律的重复性操作，直到满足某个条件。这和迭代法中反复修改某个值的操作非常一致。所以循环常用于迭代法的实现，例如二分法或者牛顿法求解方程的根。在之前的迭代法讲解中，我经常使用循环来实现编码。另外，循环语句也会经常和布尔表达式相结合。嵌套的多层循环常常用于比较多个元素的大小或者计算多个元素之间的相似度等，这也体现了排列组合的思想。 至于函数的调用，一个函数既可以调用自己，又可以调用其他函数。如果函数不断地调用自己，这就体现了递归的思想。同时，函数的递归调用也可以体现排列组合的思想。 5.1.3 基础算法介绍分治思想的时候，我谈及了MapReduce的数据切分。在分布式系统中，除了数据切分，还要经常处理的问题是：如何确定服务请求被分配到哪台机器上？这就引出了负载均衡算法，常见的包括轮询或者源地址哈希算法。轮询算法将请求按顺序轮流地分配到后端服务器上，它并不关心每台服务器当前的负载。如果给每个请求标记一个自动递增的ID，我们就可以认为轮询算法是对请求的ID进行求余操作（或者是求余的哈希函数），被除数就是可用服务器的数量，余数就是接受请求的服务器ID。而源地址哈希算法进一步扩展了这个思想，主要体现在：
不管是对何种数据进行哈希变换，也不管是何种哈希函数，只要能为每个请求确定哈希key之后，我们就能为它查找对应的服务器。 另外，第3章谈到了字符串的编辑距离，但是没有涉及字符串匹配的算法。知名的RK字符串（Rabin-Karp）匹配算法在暴力（brute force）匹配基础之上，充分利用了迭代法和哈希，提升了算法的效率。首先，RK算法可以根据两个字符串哈希后的值来判断它们是否相同。如果哈希值不同，则两个字符串肯定不同，不用再比较。此外，RK算法中的哈希设计非常巧妙，让相邻两个子字符串的哈希值产生了固定的联系，让我们可以通过前一个子字符串的哈希值推导出后一个子字符串的哈希值，这样就能使用迭代法来计算每个子字符串的哈希值，大大减少了用于哈希函数的计算。 除了分治和动态规划，另一个常用的算法思想是回溯。我们可以使用回溯来解决的问题包括八皇后和0/1背包等。回溯实际上体现了递归和排列的思想。不过，它对搜索空间做了一些优化，提前排除了不可能的情况，提升了算法整体的效率。当然，既然回溯体现了递归的思想，那么也可以将整个搜索状态表示成树，而对结果的搜索就是树的深度优先遍历。 讲到这里，我们已经对常用的数据结构、编程语句和基础算法中体现的数学思想做了一个大体的梳理。可以看到，不同的数据结构都是在编程中运用数学思维的产物。每种数据结构都有自身的特点，有利于更方便地实现某种特定的数学模型。从数据结构的角度来看，最基本的数组遍历体现了迭代的思想，而链表和树的结构可用于描述图论中的模型。栈的先进后出和队列的先进先出分别适用于图的深度优先和广度优先遍历。哈希表则充分利用了哈希函数的特点，大幅降低了查询的时间复杂度。 当然，仅使用数据结构来存储数据还不够，还需要操作这些数据。为了实现操作的流程，条件语句使用了布尔代数来控制编程逻辑，循环和函数嵌套使用迭代、递归和排列组合等思想来实现更精细的数学模型。 但是，有时候我们面对的问题太复杂了，除了数据结构和基本的编程语句，我们还需要发明一些算法。为了提升算法的效率，我们需要对其进行复杂度分析。通常，这些算法中的数学思想更为明显，因为它们都是为了解决特定的问题，根据特定的数学模型而设计的。有的时候，某个算法会体现多种数学思想，例如RK字符串匹配算法，同时使用了迭代法和哈希。此外，多种数学思维可能都是相通的。例如，递归的思想、排列的结果、二进制数的枚举都可以用树的结构来图示化，因此我们可以通过树来理解。 总之，在平时学习编程的时候，我们可以多从数学的角度出发，思考其背后的数学模型。这样不仅有利于你对现有知识的融会贯通，还可以帮助你优化数据结构和算法。既然谈到了程序的优化，那么我们还需要讨论另一个话题：复杂度分析。其实这类分析的背后也隐藏着数学的原理。 5.2 算法复杂度分析算法复杂度的分析并不简单，不过熟悉了数学原理之后，要解决相关的问题就不难了。 5.2.1 复杂度分析的原理和法则作为程序员，你一定非常清楚复杂度分析对编码的重要性。计算机系统从最初的设计、开发到最终的部署，要经过很多的步骤，而影响系统性能的因素有很多。我将这些因素分为3大类：算法理论上的计算复杂度、开发实现的方案和硬件设备的规格。如果将构建整个系统比作生产汽车，那么计算复杂度相当于在蓝图设计阶段对整个汽车的性能进行预估。如果我们能够进行准确的复杂度分析，就能从理论上预估汽车的各项指标，避免生产出一辆既耗油又开得很慢的汽车。可是，你常常会发现，要准确地分析复杂度并不容易。本节我们就用数学思维来进行系统性的复杂度分析。 1．基本概念我们先简短地回顾一下几个重要概念，便于稍后更好地理解本节的内容。算法复杂度是一个比较抽象的概念，通常只是一个估计值，它用于衡量程序在运行时所需要的资源，用于比较不同算法的性能好坏。同一段代码处理不同的输入数据所消耗的资源也可能不同，所以分析复杂度时，需要考虑3种情况，最好情况、最差情况和平均情况。 复杂度分析会考虑性能的各个方面，不过我们最关注的是两个部分，即时间和空间。时间因素是指程序执行的耗时长短，空间因素是程序占用内存或磁盘存储空间的大小。因此，我们将复杂度进一步细分为时间复杂度和空间复杂度。 我们通常所说的时间复杂度是指渐进时间复杂度，表示程序运行时间随着问题复杂度增加而变化的规律。同理，空间复杂度是指渐进空间复杂度，表示程序所需要的存储空间随着问题复杂度增加而变化的规律。我们可以使用  来表示这两者。这里通过数学的思维，总结一些比较通用的方法和法则，帮助你快速、准确地进行复杂度分析。 2．6个通用法则复杂度分析有时看上去很难，其实我们只要通过一定的方法进行系统性的分析，就能得出正确的结论。本书总结了6个法则，相信它们对你会很有帮助。 （1）四则运算法则 对于时间复杂度，代码的添加意味着计算机操作的增加，也就是时间复杂度的增加。如果代码是平行增加的，就是加法。如果是循环、嵌套或者函数的嵌套，就是乘法。 例如，在二分搜索的代码中，第一步是对长度为  的数组排序，第二步是在这个已排序的数组中进行查找。这两个部分是平行的，所以计算时间复杂度时可以使用加法。第一步的时间复杂度是  ，第二步的时间复杂度是  ，所以时间复杂度是  。再来看另外一个例子。从  个元素中选出3个元素的可重复排列，使用3层循环的嵌套或者3层递归嵌套，这里时间复杂度的计算使用乘法。由于  ，时间复杂度是  。对应加法和乘法，分别是减法和除法。如果去掉平行的代码，就减去相应的时间复杂度。如果去掉嵌套内的循环或函数，就除去相应的时间复杂度。 对于空间复杂度，同样如此。需要注意的是，空间复杂度看的是对存储空间的使用，而不是计算的次数。如果语句中没有新开辟空间，那么无论是平行增加还是嵌套增加代码，都不会增加空间复杂度。 （2）主次分明法则 这个法则主要是运用了数量级和运算法则优先级的概念。在刚刚介绍的第一个法则中，我们会对代码的不同部分所产生的复杂度进行加法或乘法。使用加法或减法时，你可能会遇到不同数量级的复杂度。这个时候，我们只需要看最高数量级的复杂度，而忽略常量、系数和较低数量级的复杂度。 在介绍二分搜索的时候，经历了先排序、后二分搜索的过程，其总的时间复杂度是  。实际上，之前给出的代码清单中还有数组初始化、变量赋值、Console输出等步骤，如果细究的话，时间复杂度应该是  ，但是和 相比，常量和 这种数量级都是可以忽略的，所以最终简化为 。 再举个例子，我们先通过随机函数生成一个长度为 的数组，然后生成这个数组的全排列。通过循环，生成 个随机数的时间复杂度为 ，而全排列的时间复杂度为 ，如果使用四则运算法则，总的时间复杂为 。不过，因为 的数量级远远大于 ，所以可以将总的时间复杂度简化为 。这对于空间复杂度同样适用。假设计算一个长度为 的向量和一个维度为 的矩阵的乘积，那么总的空间复杂度是 ，简化为 。注意，这个法则对于乘法或除法并不适用，因为乘法或除法会改变参与运算的复杂度的数量级。 （3）齐头并进法则 这个法则主要是运用了多元变量的概念，其核心思想是复杂度可能受到多个因素的影响。在这种情况下，我们要同时考虑所有因素，并在复杂度公式中体现出来。之前的章节介绍了使用动态规划解决的编辑距离问题。从解决方案的推导和代码可以看出，这个问题涉及两个因素：参与比较的第一个字符串的长度 和第二个字符串的长度 。代码使用了两次嵌套循环，第一层循环的长度为 ，第二层循环的长度为 ，根据乘法法则，时间复杂度为 。而空间复杂度很容易从推导结果的状态转移表得出，也是 。 （4）排列组合法则 排列组合的思想不仅体现在数学模型的设计中，同样也会体现在复杂度分析中，它经常会用在最好、最差和平均复杂度分析中。下面来看一个简单的算法题。 给定两个不同的字符 和 ，以及一个长度为 的字符数组。字符数组里的字符都只出现过一次，而且一定存在一个 和一个 ，请输出 和 之间的所有字符，其中包括 和 。假设我们的算法是按照数组下标值从低到高的顺序依次扫描数组，那么时间复杂度是多少呢？这里的时间复杂度是由被扫描的数组元素之数量决定的，但是要准确地求解并不容易。仔细思考一下，你会发现被扫描的元素之数量存在很多可能的值。 首先，考虑字母出现的顺序，第一个遇到的字母有两个选择， 或者 ；第二个字母只有一个选择，这就是两个元素的全排列。下面我们将两种情况分开来看。
（5）一图千言法则 在第2、3和4章中，我们提到的很多数学和算法思想都体现了树这种结构，通过画图，它们内在的联系就一目了然了。同样，这些树结构也可以帮助我们分析某些算法的复杂度。就以我们之前介绍的归并排序为例，这个算法分为数据的切分和归并两大阶段，每个阶段的数据划分不同，分组数量也不同，因此时间复杂度的计算较为复杂。下面来看一个例子。 假设待排序的数组长为 。首先，看数据切分阶段。数据切分的次数，就是切分阶段那棵树的非叶结点之数量。这个切分阶段的树是一棵满二叉树，叶结点是 个，那么非叶结点的数量就是 个，所以切分的次数也就是 次，如图5-2所示。如果切分数据的时候并不重新生成新的数据，只是生成切分边界的下标，那么时间复杂度就是 。 图5-2 个数值的二分次数 在数据归并阶段，情况稍微复杂一些。和切分不用，不同的合并步骤意味着不同的数组长度。这个时候，我们可以看到二叉树的高度为 ，如图5-3所示。另外，无论在树的哪一层，每次归并都需要扫描整个长度为 的数组，因此归并阶段的时间复杂度为 。两个阶段加起来的时间复杂度为 ，最终简化为 ，非常直观。 图5-3 个数据的归并 当然，除了图论，很多简单的图表也能帮助我们做分析。例如，在使用动态规划的时候，我们经常要画出状态转移的表格。看到这类表格，可以很容易地得出该算法的时间复杂度和空间复杂度。以编辑距离为例，参看表5-1，我们可以发现每个单元格都对应了3次计算，以及一个存储单元，而总共的单元格数量为 ，其中 为第一个字符串的长度， 为第二个字符串的长度。所以，很快就能得出这种算法的时间复杂度为 ，简化为 ，空间复杂度为 。 表5-1 动态规划的状态转移表格 （6）时空互换法则 在给定的计算量下，通常时间复杂度和空间复杂度呈数学中的反比关系。这就说明，如果无法降低整体的计算量，也许可以通过提高空间复杂度来达到降低时间复杂度的目的，或者反之，通过提高时间复杂度来降低空间复杂度。对于这个法则，最直观的例子就是缓存系统。在没有缓存系统的时候，每次请求都要服务器来处理，因此时间复杂度比较高。如果使用了缓存系统，那么会消耗更多的内存空间，但是减少了请求响应的时间。说到这，你也许会产生一个疑惑：在使用广度优先策略优化聚合操作的时候，无论是时间复杂度还是空间复杂度，都大幅降低了吗？请注意，这里时空互换法则有个前提条件，就是计算量固定。而聚合操作的优化是利用了广度优先的特点，大幅减少了整体的计算量，因此可以保证时间复杂度和空间复杂度都降低。 5.2.2 复杂度分析的案例实际工作中我们会碰到很多复杂的问题，正确地运用这些法则并不是容易的事。本节我们将结合两个案例一步步地使用这几个法则。 1．案例分析一：广度优先搜索在图遍历的4.4.2节介绍了单向广度优先搜索和双向广度优先搜索。当时我们提到了通常情况下，双向广度优先搜索性能更好。那么，应该如何从理论上分析谁的效率更高呢？先来看单向广度优先搜索。我们先快速回顾一下搜索的主要步骤。 （1）判断边界条件，时间复杂度和空间复杂度都是 。 （2）生成空的队列。对于常量级的CPU和内存操作，根据主次分明法则，时间复杂度和空间复杂度都是 。 （3）将搜索的起始结点放入队列queue和已访问结点的哈希集合visited，类似于第2步的常量级操作，其时间复杂度和空间复杂度都是 。 （4）最后也是最核心的步骤，包括while和for的两个循环嵌套。 先看时间复杂度。根据四则运算法则，时间复杂度是两个循环的次数相乘。对于嵌套在内的for循环，这个次数很好理解，和每个结点的直接连接点有关。要计算平均复杂度，就取直接连接点的平均数量，假设它为 。现在的难题在于，第一个while循环次数是多少呢？我们考虑一下齐头并进法则，是否存在其他的因素来决定计算的次数？第一次while循环，只有起始结点一个。从起始结点出发，会找到 个一度连接点，将它们放入队列，那么第二次while循环就是 次，依次类推，到第 次，那么总次数就是 。这里假设被重复访问的结点不多，可以忽略不计。在循环内部，所有操作都是常量级的，包括通过哈希集合判断是否找到终止结点。所以时间复杂度就是 ，取最高数量级 ，最后可以简化成 ，其中 是从起始结点开始所走的边数。这就是除 之外的第二个关键因素。使用一图千言法则，我们画出图5-4进行展示。 图5-4 单向广度优先搜索的展开 再来看这个步骤的空间复杂度。通过代码你应该可以看出来，只有queue和visited变量新增了数据，而图的结点本身没有发生改变。所以，考虑内存空间使用时，只需要考虑queue和visited的使用情况。两者都是在新发现一个结点时进行操作，因此新增的内存空间和被访问过的结点数成正比，同样为 。最后，上述4个步骤是平行的，所以只需要将这几个时间复杂度相加就行了。很明显前3步都是常量级操作，只有最后一步是决定性因素，因此时间复杂度和空间复杂度都是 。这里没有考虑图的生成，因为这步在单向搜索和双向搜索中是一样的，而且在实际项目中，我们也不会采用随机生成的方式。 接下来，我们来看看双向广度优先搜索，有两个关键点需要注意。 （1）双向搜索所要走的边数。如果单向需要走 条边，那么双向需要走 条边。因此时间复杂度和空间复杂度都会变为 ，简化为 。这里 中的 不能省去，因为它是在指数上，改变了数量级。仅从这一点来看，双向比单向的复杂度低。 （2）双向搜索过程中，判断是否找到通路的方式。单向搜索只需要判断一个结点是否存在集合中，每次只有 的复杂度。而双向搜索需要比较两个集合是否存在交集，其复杂度肯定要高于 。最常规的实现方法是，循环遍历其中一个集合 ，看看 中的每个元素是否出现在集合 中。假设两个集合中元素的数量都为 ，那么循环 次，时间复杂度就为 。基于这些，我们重新推导一下双向广度优先搜索的时间复杂度。 假设我们分别从结点 和 出发。从 出发，找到 个一度连接点 ，时间复杂度是 ，然后查看 是否在这 个结点中，时间复杂度是 。然后从 出发，找到 个一度连接点 ，时间复杂度是 ，然后查看 和 是否在 和 中，时间复杂度是 ，简化为 。从 继续推进到第二度的结点 ，这个时候 、 和 的并集的数量已经有 ，而 和 的并集数量只有 ，因此，针对 和 的集合进行循环更高效一些，时间复杂度是 。逐步递推下去，可以得到下面这个式子： 其中，第一项 表示找到 的时间复杂度，第二项 表示判断 是否在 中的时间复杂度，第三项 表示找到 的时间复杂度，第四项 表示判断 和 是否在 和 中的时间复杂度，以此类推。虽然这个式子简化后仍然为 ，但是我们可以通过这些推导的步骤了解整个算法运行的过程，以及对最终复杂度的影响。最后比较单向广度搜索的复杂度 和双向广度搜索的复杂度 ，双向的方法更优。 上面讨论的内容，都是假设每个结点的直接连接的结点数量都很均匀，都是 个。如果数量不是均匀的呢？我们来看几种不同的情况。 （1）用 来表示，也就是前面讨论的，不管从 和 哪个结点出发，每个结点的直接连接数量都是相当的。这个时候的最好、最差和平均复杂度非常接近。 （2）用 来表示，表示从 出发，每个结点的直接连接结点数量远远小于从 出发的那些结点数量。例如，从 出发，2度之内所有的结点都只有一两个直接连接的结点，而从 出发，2度之内的大部分结点都有100个以上的直接连接的结点。 （3）和第2种情况类似，用 表示，表示从 出发，每个结点的直接连接结点数量远远小于从 出发的那些结点数量。 对于第2种和第3种情况，双向搜索的最好、最差和平均复杂度是多少？还会是双向的方法更优吗？你可以思考一下。 2．案例分析二：全文搜索在刚才的分析中，我们已经使用了6个复杂度分析法则中的5个，不过还没涉及最后一个时空互换法则。这个法则有自己的特殊性，我们需要通过牺牲空间复杂度来降低时间复杂度，或者反之。因此，在实际运用中，更多的是使用这个法则来指导和优化系统的设计。下面我就使用搜索引擎的例子来讲一下如何做到这一点。 对于搜索引擎你一定用的很多了，它的最基本也是最重要的功能，就是根据输入的关键词查找指定的数据对象。这里以文本搜索为例。要查找某个关键词是否出现在一篇文章里，最基本的处理方式有两种。 （1）将全文作为一个很长的字符串，将用户输入的关键词作为一个子字符串，这个搜索问题就会变成子字符串匹配的问题。假设字符串平均长度为 个字符，关键词平均长度为 个字符，使用最简单的暴力法，就是将代表全文的字符串的每个字符，和关键词字符串的每个字符两两比较，那么时间复杂度就是 。 （2）对全文进行分词，将全文切分成一个个有意义的词，那么这个搜索问题就变成了将输入关键词和这些切分后的词进行匹配的问题。拉丁文分词比较简单，基本上就是根据各种分隔符来切分。而中文分词涉及很多算法，不过这不是讨论的重点。假设无论何种语言、何种分词方法，其时间复杂度都是 ，其中 为文章的长度。而在词的集合中查找输入的关键词，时间复杂度是 ， 为词集合中元素的数量。我们也可以先对词的集合排序，时间复杂度是 ，然后使用二分搜索，时间复杂度只有 。如果文章很少改变，那么全文的分词和词的排序基本上都属于一次性的开销，对于关键词查询来说，每次的时间复杂度都只有 。 无论使用上述哪种方法，看上去时间复杂都不算太高。但是我们是在海量的文章中查找信息，还需要考虑文章数量这个因素。假设文章数量是 ，那么时间复杂度就变为 ，或者 ，数量级一下子就增加了。为了降低搜索引擎在查询时候的时间复杂度，我们需要引入倒排索引（或逆向索引），这属于典型的牺牲空间来换取时间。如果你对倒排索引的概念不熟悉，我通过一个比方加以解释。假设你是一个热爱读书的人，当你进入图书馆或书店的时候，怎样快速找到自己喜爱的书籍？没错，就是看书架上的标签。如果看到一个架子上标着“计算机–编程”，那么恭喜你，离程序员的书籍就不远了。而倒排索引做的就是“贴标签”的事情。为了实现倒排索引，对于每篇文章我们都要先进行分词，然后将切分好的词作为该篇文章的标签。我们来看一下表5-2中的3篇样例文章和对应的分词，也就是标签。其中，分词之后，还做了一些标准化的处理，例如全部转成小写、去除时态等。 表5-2 文章和分词
表5-2看上去并没有什么特别。体现“倒排”的时刻来了，我们转换一下，不再从文章的角度出发，而是从标签的角度出发来看问题。也就是说，从每个标签，我们能找到哪些文章？通过这样的思考，我们可以得到表5-3。 表5-3 倒排索引
有了表5-3，就很容易知道某个关键词在哪些文章中出现。整个过程就像在哈希表中查找一样，时间复杂度只有 了。当然，我们所要付出的成本就是倒排索引这张表。假设有 个不同的单词，而每个单词所对应的文章平均数为 的话，那么这种索引的空间复杂度就是 。好在 和 通常不会太大，对内存和磁盘空间的消耗都是可以接受的。 本文摘自《程序员的数学基础课：从理论到Python实践》 本书紧贴计算机领域，从程序员的需求出发，精心挑选了程序员真正用得上的数学知识，通过生动的案例来解读知识中的难点，使程序员更容易对实际问题进行数学建模，进而构建出更优化的算法和代码。 本书共分为三大模块：“基础思想”篇梳理编程中常用的数学概念和思想，既由浅入深地精讲数据结构与数学中基础、核心的数学知识，又阐明数学对编程和算法的真正意义；“概率统计”篇以概率统计中核心的贝叶斯公式为基点，向上讲解随机变量、概率分布等基础概念，向下讲解朴素贝叶斯，并分析其在生活和编程中的实际应用，使读者真正理解概率统计的本质，跨越概念和应用之间的鸿沟；“线性代数”篇从线性代数中的核心概念向量、矩阵、线性方程入手，逐步深入分析这些概念是如何与计算机融会贯通以解决实际问题的。除了理论知识的阐述，本书还通过Python语言，分享了通过大量实践积累下来的宝贵经验和编码，使读者学有所用。 本书的内容从概念到应用，再到本质，层层深入，不但注重培养读者养成良好的数学思维，而且努力使读者的编程技术实现进阶，非常适合希望从本质上提升编程质量的中级程序员阅读和学习。 |
|
|
来自： taotao_2016 > 《计算机》
