数据结构与算法图解

• 2025/04/18 认为好看：非常好的算法和数据结构入门书籍！虽然书中讲述很多的东西之前都有学过，但我之前学习起来觉得数据结构之间没什么联系，都是一个个独立的知识点。本书做的非常好的一点是，通过循循善诱，从之前简单数据结构的铺垫中自然而然地引出复杂数据结构，给我一种“原来这种数据结构是在其他数据结构的基础上，为了适应某些应用场景，而发明出来的！”的感觉。

前言

• 第1章和第2章，解释数据结构和算法是什么，并探索时间复杂度这一判断算法效率的概念。此过程中还会经常提及数组、集合和二分查找。
• 第3章，以老奶奶都听得懂的方式去揭示大O记法的本质。因为大O记法全书都会用到，所以对这一章的理解非常重要。
• 第4章、第5章和第6章，进一步探索大O记法，并以实例来演示如何利用它来加快代码运行速度。这一路上，我们还会提到各种排序算法，包括冒泡排序、选择排序和插入排序。
• 第7章和第8章会再探讨几种数据结构，包括散列表、栈和队列，展示它们对代码速度和可读性的影响，并学会用其解决实际问题。
• 第9章会介绍递归，计算机科学中的核心概念。我们会对其进行分解，考察它在某些问题上的利用价值。第10章会运用递归来实现一些飞快的算法，例如快速排序和快速选择，提升读者的算法开发能力。
• 第11章、第12章和第13章会探索基于结点的数据结构，包括链表、二叉树和图，并展示它们在各种应用中的完美表现。
• 最后一章，第14章，介绍空间复杂度。当程序运行环境的内存空间不多，或处理的数据量很大时，理解空间复杂度便显得特别重要。
• 有时候，理解一个复杂概念的最好方法就是把它拆分成小块，并且在完全明白某一块以后才去着手其他部分。

第1章 数据结构为何重要

• 编程基本上就是在跟数据打交道。计算机程序总是在接收数据、操作数据或返回数据。
• 数据结构不只是用于组织数据，它还极大地影响着代码的运行速度。

1.1 基础数据结构：数组

• 数组是计算机科学中最基本的数据结构之一。
• 我们会用一些名为索引的数字来标识每项数据在数组中的位置。
• 读取：查看数据结构中某一位置上的数据。对于数组来说，这意味着查看某个索引所指的数据值。
• 查找：从数据结构中找出某个数据值的所在。对于数组来说，这意味着检查其是否包含某个值，如果包含，那么还得给出其索引。
• 插入：给数据结构增加一个数据值。对于数组来说，这意味着多加一个格子并填入一个值。
• 删除：从数据结构中移走一个数据值。对于数组来说，这意味着把数组中的某个数据项移走。
• 操作的速度，并不按时间计算，而是按步数计算。
• 操作的速度，也常被称为时间复杂度。在本书中，我们会提到速度、时间复杂度、效率、性能，但它们其实指的都是步数。
• 当程序声明一个数组时，它会先划分出一些连续的空格子以备使用。换句话说，如果你想创建一个包含5个元素的数组，计算机就会找出5个排成一行的空格子，将其当成数组。
• 内存地址就只用一个普通的数字来表示。而且，每个格子的内存地址都比前一个大1
• [插图]
• (1) 计算机可以一步就跳到任意一个内存地址上。
• (2) 数组本身会记有第一个格子的内存地址，因此，计算机知道这个数组的开头在哪里。
• (3) 数组的索引从0算起。
• (1) 该数组的索引从0算起，其开头的内存地址为1010。(2) 索引3在索引0后的第3个格子上。(3) 于是索引3的内存地址为1013，因为1010 + 3=1013。
• 所以，数组的读取是一种非常高效的操作，因为它只要一步就好。一步自然也是最快的速度。这种一步读取任意索引的能力，也是数组好用的原因之一。
• 想要查找数组中是否存在某个值，计算机会先从索引0开始，检查其值，如果不匹配，则继续下一个索引，以此类推，直至找到为止。
• 逐个格子去检查的做法，就是最基本的查找方法——线性查找。
• 无论是多长的数组，查找都比读取要慢，因为读取永远都只需要一步，而查找却可能需要多步。
• 在数组开头或中间插入，就另当别论了。这种情况下，我们需要移动其他元素以腾出空间，于是得花费额外的步数。
• 一个含有N个元素的数组，其插入数据的最坏情况会花费N + 1步。即插入在数组开头，导致N次移动，加上一次插入。
• 数组中间是不应该有空格的，所以，我们得把”dates”和”elderberries”往左移。
• 删除本身只需要1步，但接下来需要额外的步骤将数据左移以填补删除所带来的空隙。
• 对于含有N个元素的数组，删除操作最多需要N步。

1.2 集合：一条规则决定性能

• 集合：它是一种不允许元素重复的数据结构。
• 集合是有不同形式的，但现在我们只讨论基于数组的那种。这种集合跟数组差不多，都是一个普通的元素列表，唯一的区别在于，集合不允许插入重复的值。
• 集合就是用于确保数据不重复。
• 计算机知道集合开头的内存地址，所以能够一步跳到集合的任意索引。
• 集合的查找也跟数组的查找无异，需要N步去检查某个值在不在集合当中。删除也是，总共需要N步去删除和左移填空。
• 对于集合，计算机得先确定要插入的值不存在于其中——因为这就是集合：不允许重复值。于是每次插入都要先来一次查找。
• 最坏的情况则是在集合的开头插入，这时计算机得检查N个格子以保证集合不包含那个值，然后用N步来把所有值右移，最后再用1步来插入新值。总共2N + 1步。

1.3 总结

• 理解数据结构的性能，关键在于分析操作所需的步数。
• 不同的数据结构有不同的时间复杂度，类似地，不同的算法（即使是用在同一种数据结构上）也有不同的时间复杂度。

第2章 算法为何重要

• 选择合适的数据结构将会显著地提升代码的性能。即使是像数组和集合这样相似的两种数据结构，在高负荷的运行环境下也会表现得天差地别。
• 算法这个词听起来很深奥，其实不然。它只是解决某个问题的一套流程。
• 在计算机的世界里，算法则是指某项操作的过程。
• 一种操作会有多种算法的实现。

2.1 有序数组

• 有序数组跟上一章讨论的数组几乎一样，唯一区别就是有序数组要求其值总是保持有序
• 往有序数组中插入新值，需要先做一次查找以确定插入的位置。这是它跟常规数组的关键区别（在性能方面）之一。

2.2 查找有序数组

• 从左至右，逐个格子检查，直至找到。这种方式称为线性查找。
• 有序数组的线性查找大多数情况下都会快于常规数组。
• 其实，线性查找只不过是查找算法的其中一种而已。
• 有序数组相比常规数组的一大优势就是它可以使用另一种查找算法。此种算法名为二分查找，它比线性查找要快得多。

2.3 二分查找

• 有序数组相比常规数组的一大优势就是它除了可以用线性查找，还可以用二分查找。
• 因为数组的长度是已知的，将长度除以2，我们就可以跳到确切的内存地址上，然后检查其值。

2.4 二分查找与线性查找

• 有序数组并不是所有操作都比常规数组要快。如你所见，它的插入就相对要慢。衡量起来，虽然插入是慢了一些，但查找却快了许多。还是那句话，你得根据应用场景来判断哪种更合适。

第3章 大O记法

3.1 大O：数步数

• 大O不关注算法所用的时间，只关注其所用的步数。
• O(1)意味着一种算法无论面对多大的数据量，其步数总是相同的。
• “大O记法可用来描述一个函数的增长率的上限”，或者“如果函数g(x)的增长速度不比函数f(x)快，那么就称g属于O(f)”。
• Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest和Clifford Stein所著的《算法导论》

3.2 常数时间与线性时间

• 从 O(N)可以看出，大 O记法不只是用固定的数字（如22、440）来表示算法的步数，而是基于要处理的数据量来描述算法所需的步数。或者说，大O解答的是这样的问题：当数据增长时，步数如何变化？
• 也就是说，数据越多，算法所需的步数就越多。O(N)也被称为线性时间。
• O(1)也被称为常数时间。
• 算法的步数都恒定，所以这也是常数时间，也可以表示为O(1)。
• O(1)就是用来表示所有数据增长但步数不变的算法。

3.3 同一算法，不同场景

• 概括来说，线性查找的最好情况是O(1)，最坏情况是O(N)。
• 大 O记法一般都是指最坏情况。
• 知道各种算法会差到什么程度，能使我们做好最坏打算，以选出最适合的算法。

3.4 第三种算法

• 二分查找的大O记法是：O(logN)
• 归于此类的算法，它们的时间复杂度都叫作对数时间。
• O(log N)意味着该算法当数据量翻倍时，步数加1。

3.5 对数

• 对数是指数的反函数
• log28则将上述计算反过来，它意思是：要把2乘以自身多少次，才能得到8。因为需要3次，所以，log28=3。
• log28可以表达为：将8不断地除以2直到1，需要多少个2。
• 或者说，将8不断地除以2，要除多少次才能到1呢？答案是3，所以，log28=3。

3.6 解释O(log N)

• O(logN)则代表算法处理N个元素需要log2N步。
• O(log N)算法的步数等于二分数据直至元素剩余1个的次数。

3.7 实例

• 不管一段代码做什么事情，技术上来说它都是一个算法——因为它是解决某种问题的一个独特的过程。

第4章 运用大O来给代码提速

• 大O记法能客观地衡量各种算法的时间复杂度，是比较算法的利器。
• 有了大O的话，你就可以与其他常用的算法比较，然后问自己：“我的算法跟它们相比，是快还是慢？”

4.1 冒泡排序

• 如何将一个无序的数字数组整理成升序？
• 冒泡排序是一种很基本的排序算法，步骤如下。(1) 指向数组中两个相邻的元素（最开始是数组的头两个元素），比较它们的大小。插图 如果它们的顺序错了（即左边的值大于右边），就互换位置。[插图]如果顺序已经是正确的，那这一步就什么都不用做。(3) 将两个指针右移一格。[插图]重复第(1)步和第(2)步，直至指针到达数组末尾。(4)重复第(1)至(3)步，直至从头到尾都无须再做交换，这时数组就排好序了。

4.3 冒泡排序的实现

• 变量unsorted_until_index表示“该索引之前的数据都没排过序”。
• 我们先将sorted初步设置为True。当发生任何交换时，我们会将其改为False。如果在一次轮回里没有做过交换，那么sorted就确定为True，我们知道数组已排好序了。
• 此循环中，我们会比较相邻的元素，如果有顺序错误，就会进行交换，并将sorted改为False。

4.4 冒泡排序的效率

• 冒泡排序的执行步骤可分为两种。比较：比较两个数看哪个更大。交换：交换两个数的位置以使它们按顺序排列。
• 冒泡排序效率的大O记法，是O(N2)。

4.5 二次问题

• 嵌套循环算法的效率就是O(N2)。一旦看到嵌套循环，你就应该马上想到O(N2)。
• 当遇到低效的算法时，我们都应该花些时间思考下有没有更快的做法。特别是当数据量巨大的时候，优化不足的应用甚至可能会突然挂掉。尽管这可能已经是最佳方案，但你还是要确认一下。

4.6 线性解决

• 2025/04/17 发表想法：空间换时间了。

采用第二种算法能极大地提升hasDuplicateValue的效率。如果这个程序处理的数据量很大，那么性能差别是很明显的（其实第二种算法有一个缺点，不过我们在最后一章才会讲到）。

第5章 用或不用大O来优化代码

• 有时候即使两种算法的大O记法完全一样，但实际上其中一个比另一个要快得多。

5.1 选择排序

• 选择排序的步骤如下。(1) 从左至右检查数组的每个格子，找出值最小的那个。
• (2) 知道哪个格子的值最小之后，将该格与本次检查的起点交换。第1次检查的起点是索引0，第2次是索引1，以此类推。

5.3 选择排序的实现

• 外层的循环代表每一轮检查。在一轮检查之初，我们会先记住目前的最小值的索引。
• 我们实际上记录的是最小值的索引，而非最小值本身。
• 遇到比之前记录的本轮最小值还小的格子值，就将lowestNumberIndex更新为该格子的索引。
• 内层循环结束时，会得到未排序数值中最小值的索引。
• 然后再看看这个最小值是否已在正确位置，即该索引是否等于i。如果不是，就将i所指的值与最小值交换。

5.4 选择排序的效率

• 选择排序的步骤可分为两类：比较和交换，也就是在每轮检查中把未排序的值跟该轮已遇到的最小值做比较，以及将最小值与该轮起点的值交换以使其位置正确。
• 选择排序的步数大概只有冒泡排序的一半，即选择排序比冒泡排序快一倍。

5.5 忽略常数

• 选择排序的大O记法跟冒泡排序是一样的。
• 选择排序的大O记法为O(N2)，跟冒泡排序一样。这是因为大O记法的一条重要规则我们至今还没提到：大O记法忽略常数。
• 严格来说本应为O(N2/ 2)，最终得写成O(N2)。类似地，O(2N)要写成O(N);O(N/2)也写成O(N)；就算是比O(N)慢100倍的O(100N)，也要写成O(N)。

5.6 大O的作用

• 尽管不能比较冒泡排序和选择排序，大O还是很重要的，因为它能够区分不同算法的长期增长率。当数据量达到一定程度时，O(N)的算法就会永远快过 O(N2)，无论这个 O(N)实际上是O(2N)还是O(100N)。即使是O(100N)，这个临界点也是存在的。
• 当两种算法落在不同的大 O类别时，你就很自然地知道应该选择哪种。因为在大数据的情况下，必然存在一临界点使这两种算法的速度永远区分开来。
• 大O记法非常适合用于不同大 O分类下的算法的对比，对于大O同类的算法，我们还需要进一步的解析才能分辨出具体差异。

5.7 一个实例

• 这种做法的while循环会跳过间隔的元素，因此避免了检查每个元素。结果就是有N个元素，会有N / 2次读取，N / 2次插入。它跟第一种做法一样，记为O(N)。

5.8 总结

• 至今我们关注的都是最坏情况下算法会跑得多慢，但其实最坏情况并不总会发生。

第6章 乐观地调优

• 最坏情况不是唯一值得考虑的情况。全面分析各种情况，能帮助你为不同场景选择适当的算法。

6.3 插入排序的实现

• 以下是插入排序的Python实现。

def insertion_sort(array):
    for index in range(1, len(array)):
        position=index
        temp_value=array[index]
        while position > 0 and array[position -1] > temp_value:
            array[position]=array[position -1]
            position=position-1
            array[position]=temp_value

6.4 插入排序的效率

• temp_value的移除跟插入在每一轮里都会各发生一次。因为总是有N -1轮，所以可以得出结论：有N -1次移除和N -1次插入。
• 大O只保留最高阶的N。
• 在最坏的情况里，插入排序的时间复杂度跟冒泡排序、选择排序一样，都是O(N2)。
• 虽然冒泡排序和选择排序都是O(N2)，但选择排序实际上是N2/ 2步，比N2步的冒泡排序更快。乍一看，你可能会觉得插入排序跟冒泡排序一样，因为它们都是O(N2)，其实插入排序是N 2+ 2N -2步。
• 如果本书到此为止，你或许会认为比冒泡排序和插入排序快一倍的选择排序是三者中最优的，但事情并没有这么简单。

6.5 平均情况

• 最好情况和最坏情况很少发生。现实世界里，最常出现的是平均情况。
• 完全降序的最坏情况之前已经见过，它每一轮都要比较和平移所遇到的值（这两种操作合计N2步）。对于完全升序的最好情况，因为所有值都已在其正确的位置上，所以每一轮只需要一次比较，完全不用平移。
• 插入排序的性能在不同场景中差异很大。最坏、平均、最好情况，分别需要 N2、N2/ 2、N步。
• 选择排序是无论何种情况，最坏、平均、最好，都要N2/ 2步。因为这个算法没有提早结束某一轮的机制，不管遇到什么，每一轮都得比较所选索引右边的所有值。
• 如果你确信数组是大致有序的，那么插入排序比较好。如果是大致逆序，则选择排序更快。

6.6 一个实例

• break可以中断内部循环，节省步数和时间。
• 在数组不同但有部分重复的平均情况下，步数会介于N到N2之间。

6.7 总结

• 懂得区分最好、平均、最坏情况，是为当前场景选择最优算法以及给现有算法调优以适应环境变化的关键。记住，虽然为最坏情况做好准备十分重要，但大部分时间我们面对的是平均情况。

第7章 查找迅速的散列表

• 一种名为散列表的数据结构，只用O(1)步就能找出数据。

7.1 探索散列表

• 但在不同的语言中，它有不同的名字，除了散列表，还有散列、映射、散列映射、字典、关联数组。
• 散列表由一对对的数据组成。一对数据里，一个叫作键，另一个叫作值。
• 在散列表中查找值的平均效率为O(1)，因为只要一步。

7.2 用散列函数来做散列

• 将字符串转为数字串的过程就是散列，其中用于对照的密码，就是散列函数。
• 一个散列函数需满足以下条件才有效：每次对同一字符串调用该散列函数，返回的都应是同一数字串。如果每次都返回不一样的结果，那就无效。
• 经由此函数转换，DAB也会得到8，跟BAD一样。这确实会带来一些问题，我们之后会说明。

7.3 一个好玩又赚钱的同义词典

• 散列表就是一堆成对的元素。
• 计算机用散列函数对键进行计算。
• 2025/04/17 发表想法：map的底层还是数组，散列函数是为了计算键对应的数组索引

“bad”的散列值为8，于是计算机将”evil”放到第8个格子里。

• “bad”的散列值为8，于是计算机将”evil”放到第8个格子里。
• (1) 计算这个键的散列值：BAD=2×1×4=8。(2) 由于结果是8，因此去到第8格并返回其中的值。在本例中，该值为”evil”。

7.4 处理冲突

• 2025/04/17 发表想法：哈希冲突，解决方法有很多，比如使用红黑树

往已被占用的格子里放东西，会造成冲突。

• 2025/04/17 发表想法：这种方式带来的问题是，最坏情况下，某个哈希值对应的数组特别长，导致算法性能退化为ON

一种经典的做法就是分离链接。当冲突发生时，我们不是将值放到格子里，而是放到该格子所关联的数组里。

• 该数组又以子数组构成，每个子数组含两个元素，第一个是被检索的词，后一个是其相应的同义词。
• (1) 计算散列值DAB=4×1×2=8。(2) 读取第8格，发现其中不是一个单独的值，而是一个数组。(3) 于是线性地在该数组中查找，检查每个子数组的索引0位置，如果碰到要找的词（“dab”），就返回该子数组的索引1的值。
• 如果数据都刚好存在同一个格子里，那么查找就相当于在数组上进行。因此散列表的最坏情况就是O(N)。

7.5 找到平衡

• 归根到底，散列表的效率取决于以下因素。要存多少数据。有多少可用的格子。用什么样的散列函数。
• 如果要放的数据很多，格子却很少，就会造成大量冲突，导致效率降低。
• 一个好的散列函数，应当能将数据分散到所有可用的格子里去。
• 尽管100个格子能很好地避免冲突，但只用来放5个值的话，就太浪费空间了。这就是使用散列表时所需要权衡的：既要避免冲突，又要节约空间。
• 要想解决这个问题，可参考计算机科学家研究出的黄金法则：每增加7个元素，就增加10个格子。
• 数据量与格子数的比值称为负载因子。把这个术语代入刚才的理论，就是：理想的负载因子是0.7（7个元素 / 10个格子）。

7.6 一个实例

• 集合——一种能保证元素不重复的数组。每次往其中插入新元素时，都要先做一次线性查找来确定该元素是否已存在（如果是无序数组）。
• 很多时候，我们都可以把散列表当成集合来用。
• 把数组作为集合的话，数据是直接放到格子里的。用散列表时，则是将数据作为键，值可以为任何形式，例如数字1，或者布尔值true也行。
• 每次插入新值，都只需花O(1)的时间，而不是线性查找的O(N)。即使数据已存在时也是这个速度。
• 再次插入”banana”时，我们并不需要检查它存在与否，因为即使存在，也只是将其对应的值重写成1。
• 散列表确实非常适用于检查数据的存在性。
• 使用类似的逻辑，但换成散列表（在Javascript里叫作对象），就可以处理字符串了。

7.7 总结

• 有些数据结构的优点并不在于性能
• 下一章就研究两种能帮助改善代码可读性和可维护性的数据结构。

第8章 用栈和队列来构造灵巧的代码

• 掌握多种数据结构还有助于简化代码，提高可读性。
• 栈和队列。事实上它们并不是全新的东西，只不过是多加了一些约束条件的数组而已。
• 具体一点说，栈和队列都是处理临时数据的灵活工具。在操作系统、打印任务、数据遍历等各种需要临时容器才能构造出美妙算法的场景，它们都大有作为。
• 临时数据就是一些处理完便不再有用的信息，因此没有保留的必要。
• 栈和队列就正好能把数据按顺序处理，并在处理完成后将其抛弃。

8.1 栈

• 栈存储数据的方式跟数组一样，都是将元素排成一行。只不过它还有以下3条约束。只能在末尾插入数据。只能读取末尾的数据。只能移除末尾的数据。
• 你可以将栈看成一叠碟子：你只能看到最顶端那只碟子的碟面，其他都看不到。另外，要加碟子只能往上加，不能往中间塞，要拿碟子只能从上面拿，不能从中间拿（至少你不应该这么做）
• 。绝大部分计算机科学家都把栈的末尾称为栈顶，把栈的开头称为栈底。
• 往栈里插入数据，也叫作压栈。你可以想象把一个碟子压在其他碟子上的画面。
• 栈的特性：只能在末尾插入数据。
• 从栈顶移除数据叫作出栈。这也是栈的限制：只能移除末尾的数据。
• 压栈和出栈可被形容为LIFO（last in, first out）后进先出。解释起来就是最后入栈的元素，会最先出栈。

8.2 栈实战

• 栈很少用于需要长期保留数据的场景，却常用于各种处理临时数据的算法。
• (1) 如果读到的字符不是任一种括号（圆括号、方括号、花括号），就忽略它，继续下一个。
• (2) 如果读到左括号，就将其压入栈中，意味着后面需要有对应的右括号来做闭合。
• (3) 如果读到右括号，就查看栈顶的元素，并做如下分析。
  • 如果栈里没有任何元素，也就是遇到了右括号但没有左括号，即第2类语法错误。
  • 如果栈里有数据，但与刚才读到的右括号类型不匹配，那就是第3类语法错误。
  • 如果栈顶元素是匹配的左括号，则表示它已经闭合。那么就可以将其弹出，因为已经不需要再记住它了。
• (4) 如果一行代码读完，栈里还留有数据，那就表示存在左括号，没有右括号与之匹配，即第1类语法错误。
• Ruby的数组自带push和pop方法，是在数组结尾插入和删除元素的便捷调用。只使用这两个方法的话，数组便形同于栈。
• 栈被巧妙地用来跟踪那些还没有配对的左括号。
• 当数据的处理顺序要与接收顺序相反时（LIFO），用栈就对了。

8.3 队列

• 你可以将队列想象成是电影院排队。排在最前面的人会最先离队进入影院。套用到队列上，就是首先加入队列的，将会首先从队列移出。因此计算机科学家都用缩写“FIFO”（first in, first out）先进先出，来形容它。
• 队列也有3个限制（但内容不同）。只能在末尾插入数据（这跟栈一样）。只能读取开头的数据（这跟栈相反）。只能移除开头的数据（这也跟栈相反）。

8.4 队列实战

• 2025/04/17 发表想法：消息队列!

队列应用广泛，从打印机的作业设置，到网络应用程序的后台任务，都有队列的存在。

• Ruby数组的push方法，将数据加到数组末尾，以及shift方法，将数据从数组开头移除。
• 2025/04/17 发表想法：go语言的channel也是一种队列吗？

队列也是处理异步请求的理想工具——它能保证请求按接收的顺序来执行。

8.5 总结

• 掌握了栈和队列，就解锁出了下一个目标：学习基于栈的递归。递归也是其他高级算法的基础，我们将会在本书余下的部分讲解它们。

第9章 递归

• 函数调用自身，就叫作递归。无限递归用处不大，甚至还挺危险，但是有限的递归很强大。

9.1 用递归代替循环

• countdown里并没有任何循环结构，它通过调用自身就能够从10开始倒数并将每个数字打印出来。
• 几乎所有循环都能够转换成递归。但能用不代表该用。

9.2 基准情形

• 在递归领域（真有这么一个地方），不再递归的情形称为基准情形。对于刚才的countdown()函数来说，0就是基准情形。

9.3 阅读递归代码

• (1) 找出基准情形。(2) 看该函数在基准情形下会做什么。(3) 看该函数在到达基准情形的前一步会做什么。(4) 就这样往前推，看每一步都在做什么。
• 第二条路的factorial有调用自身，是递归发生的地方。
• 第一条路并没有调用自身，因此这里是基准情形。
• 如你所见，这种从基准情形入手再往上分析的思路，对理解递归代码是多么有益。

9.4 计算机眼中的递归

• 计算机是用栈来记录每个调用中的函数。这个栈就叫作调用栈。
• 起初计算机调用的是factorial(3)。然而，在该方法完成之前，它又调用了factorial(2)。为了记住自己还在factorial(3)中，计算机将此事压入调用栈中。[插图]接着计算机开始处理factorial(2)。该factorial(2)会调用factorial(1)。不过在进入factorial(1)前，计算机得记住自己还在factorial(2)中，于是，它将此事也压入调用栈中。[插图]然后计算机执行factorial(1)。因为1已经是基准情形了，所以它可以返回，不用再调用factorial。
• 尽管factorial(1)结束了，但调用栈内仍存在数据，意味着整件事还没完，计算机还处于其他函数当中。你应该还记得，栈的规定是只有栈顶元素（即最后的元素）才能被看到。所以，计算机接下来就去检查了调用栈的栈顶，发现那是factorial(2)。由于factorial(2)是调用栈的最后一项，因此代表最近调用并且最应该先完成的是factorial(2)。于是计算机将factorial(2)从调用栈弹出。[插图]并将其结束。然后计算机再次检查调用栈，看下一步应该结束哪个方法。调用栈如下所示。[插图]于是计算机将factorial(3)从调用栈弹出，并将其结束。到这里，调用栈就清空了，计算机也因此得知所有方法都执行完了，递归结束。
• (1) factorial(3)被第一个调用。(2) factorial(2)被第二个调用。(3) factorial(1)被第三个调用。(4) factorial(1)被第一个完成。(5) factorial(2)在factorial(1)的基础上完成。(6) 最后，factorial(3)在factorial(2)的基础上完成。有趣的是，无限递归（如本章开头的例子）的程序会一直将同一方法加到调用栈上，直到计算机的内存空间不足，最终导致栈溢出的错误。

9.5 递归实战

• 递归可以自然地用于实现那些需要重复自身的算法。
• 这里的“所有文件”，不仅指的是该目录中的文件，还包括其子目录的文件，以及子目录里的子目录的文件，以此类推。
• 改用递归并不会改变算法的大O。但是，在下一章你会看到，递归可以作为算法的核心组件，影响算法的速度。

9.6 总结

• 递归十分适用于那些无法预估计算深度的问题。

第10章 飞快的递归算法

• 大多数编程语言都自带用于数组排序的函数，其中很多采用的都是快速排序。
• 快速排序依赖于一个名为分区的概念，所以我们先从它开始了解。

10.1 分区

• 此处的分区指的是从数组随机选取一个值，以其为轴，将比它小的值放到它左边，比它大的值放到它右边。
• (1) 左指针逐个格子向右移动，当遇到大于或等于轴的值时，就停下来。(2) 右指针逐个格子向左移动，当遇到小于或等于轴的值时，就停下来。(3) 将两指针所指的值交换位置。(4) 重复上述步骤，直至两指针重合，或左指针移到右指针的右边。(5) 将轴与左指针所指的值交换位置。
• 比较左指针和轴。由于左指针的值比轴要大，我们将其停在那里。而且现在左指针与右指针重合，无须再移动指针了。

10.2 快速排序

• 快速排序严重依赖于分区。
• (1) 把数组分区。使轴到正确的位置上去。(2) 对轴左右的两个子数组递归地重复第1、2步，也就是说，两个子数组都各自分区，并形成各自的轴以及由轴分隔的更小的子数组。然后也对这些子数组分区，以此类推。(3) 当分出的子数组长度为0或1时，即达到基准情形，无须进一步操作。
• 左右指针只能同时指向6。[插图]第18步：比较左指针（值为6）与轴（值为5）。由于6大于轴，左指针不再右移。第19步：本来指着6的右指针应该左移，但6的左边已经没有其他元素了，所以右指针停止。由于左指针与右指针重合，也不用再做任何移动了，可以跳到最后一步。第20步：将左指针的值与轴交换。

10.3 快速排序的效率

• [插图]
• 只含1个元素的子数组就是基准情形，无须任何交换和比较，所以只有元素量大于或等于2的子数组才要算分区。
• O(N log N)算法。
• 如果数组元素有N个，那就是log N次。假设元素有8个，那就要对半切3次，才能分出只有1个元素的子数组。
• 因为等分发生了log N次，而每次都要对总共N个元素做分区，所以总步数为N×log N。

10.4 最坏情况

• 快速排序最坏的情况就是每次分区都使轴落在数组的开头或结尾。
• 快速排序最坏情况下的效率为O(N2)。
• 虽然快速排序在最好情况和最坏情况都没能超越插入排序，但在最常遇见的平均情况，前者的O(N log N)比后者的O(N2)好得多，所以总体来说，快速排序优于插入排序。

10.5 快速选择

• 假设有一个无序的数组，你不需要将它排序，只要找出里面第10小的值，或第5大的值。
• 快速选择需要对数组分区，这跟快速排序类似，或者你可以把它想象成是快速排序和二分查找的结合。
• 现在轴已安放在正确位置了，因为那是第5个格子，所以我们掌握了数组第5小的值是什么。虽然我们要找的是第2小的值，但刚才的操作足以让我们忽略轴右侧的那些元素，将查找范围缩小到轴左侧的子数组上。这看起来就像是不断地把查找范围缩小一半的二分查找。
• 快速选择的优势就在于它不需要把整个数组都排序就可以找到正确位置的值。
• 分析快速选择的效率，你会发现它的平均情况是O(N)。

10.6 总结

• 由于运用了递归，快速排序和快速选择可以将棘手的问题解决得既巧妙又高效。
• 其实能递归的不只有算法，还有数据结构。后面几章将要接触的链表、二叉树以及图，就利用了自身递归的特性，给我们提供了迅速的数据操作方式。

第11章 基于结点的数据结构

• 基于结点的数据结构拥有独特的存取方式，因此在某些时候具有性能上的优势。
• 虽然链表和数组看上去差不多，但在性能上却各有所长。

11.1 链表

• 事实上，能用数组来做的事情，一般也可以用链表来做。然而，链表的实现跟数组是不一样的，在不同场景它们会有不同的性能表现。
• 当要创建数组时，程序会在内存中找出一组连续的空格子，给它们起个名字，以便你的应用存放数据
• 计算机能够直接跳到数组的某一索引上。如果代码要求它读取索引4的值，那么计算机只需一步就可以完成任务。重申一次，之所以能够这样，是因为程序事先知道了数组开头所在的内存地址——例如地址是1000——当它想去索引4时，便会自动跳到1004处。
• 与数组不同的是，组成链表的格子不是连续的。它们可以分布在内存的各个地方。这种不相邻的格子，就叫作结点。
• 每个结点除了保存数据，它还保存着链表里的下一结点的内存地址。
• 此例中，我们的链表包含4项数据：“a”、“b”、“c”和”d”。因为每个结点都需要2个格子，头一格用作数据存储，后一格用作指向下一结点的链（最后一个结点的链是null，因为它是终点），所以整体占用了8个格子。
• 若想使用链表，你只需知道第一个结点在内存的什么位置。因为每个结点都有指向下一结点的链，所以只要有给定的第一个结点，就可以用结点1的链找到结点2，再用结点2的链找到结点3……如此遍历链表的剩余部分。
• 链表相对于数组的一个好处就是，它可以将数据分散到内存各处，无须事先寻找连续的空格子。

11.2 实现一个链表

• Node类有两个属性：data表示结点所保存的数据，next_node表示指向下一结点的链
• LinkedList的作用就是一个指针，它指向链表的第一个结点。

11.3 读取

• 因为计算机得从第一个结点开始，沿着链一直读到最后一个结点，于是需要N步。由于大O记法默认采用最坏情况，所以我们说读取链表的时间复杂度为O(N)。这跟读取数组的O(1)相比，的确是一大劣势。

11.4 查找

• 所谓查找就是从列表中找出某个特定值所在的索引。

11.5 插入

• 在某些情况下，链表的插入跟数组相比，有着明显的优势。回想插入数组的最坏情况：当插入位置为索引0时，因为需要先将插入位置右侧的数据都右移一格，所以会导致 O(N)的时间复杂度。然而，若是往链表的表头进行插入，则只需一步，即O(1)。
• 要在表头增加”yellow”，我们只需创建一个新的结点，然后使其链接到”blue”那一结点。
• 因为无须平移其他数据，所以与数组相比，链表在前端插入数据更为便捷。
• 在该动作之前，计算机还得先找到索引1的结点（“blue”），让结点1的链指向新的结点。这个过程就是之前所说的读取链表，其效率为O(N)。
• 链表的插入效率为O(N)，与数组一样。
• 通过以上分析，你会发现链表的最坏情况和最好情况与数组刚好相反。在链表开头插入很方便，在数组开头插入却很麻烦；在数组的末尾插入是最好情况，在链表的末尾插入却是最坏情况。

11.6 删除

• 从效率上来看，删除跟插入是相似的。如果删除的是链表的第一个结点，那就只要1步：将链表的first_node设置成当前的第二个结点。
• 删除链表的最后一个结点，其实际的删除动作只需1步——令倒数第二的结点的链指向null。然而，要找出倒数第二的结点，得花 N步，因为我们依然只能从第一个结点顺着链往下一个个地找。
• 尽管两者的查找、插入、删除的效率看起来差不多，但在读取方面，数组比链表要快得多。既然如此，那为什么还要用链表呢？

11.7 链表实战

• 高效地遍历单个列表并删除其中多个元素，是链表的亮点之一。
• 用数组的话，每次删除邮件地址，我们就要另外再花 O(N)步去左移后面的数据，以填补删除所产生的空隙。而且还必须完成这些平移才能执行下一次邮件地址的检查。

11.8 双向链表

• 链表的另一个引人注目的应用，就是作为队列的底层数据结构。
• 第8章我们已经介绍过队列，你应该还记得它就是一种只能在末尾插入元素，在开头删除元素的数据结构。当时我们用数组作为队列的底层，并解释说队列只是有约束条件的数组。其实，改用链表来做队列的底层也可以，同样地，只要使该链表的元素只在末尾插入，并在开头删除就好了。
• 队列插入数据只能在末尾。
• 在数组的末尾插入是极快的，时间复杂度为O(1)。链表则要O(N)。所以在插入方面，选择数组比链表更好。但到了删除的话，就是链表更快了，因为它只要O(1)，而数组是O(N)。
• 然而，要是采用双向链表这一链表的变种，就能使队列的插入和删除都为O(1)。
• 双向链表跟链表差不多，只是它每个结点都含有两个链——一个指向下一结点，另一个指向前一结点。此外，它还能直接访问第一个和最后一个结点。
• 以下是一个双向链表。[插图]
• 由于双向链表总会记住第一个和最后一个结点，因此能够一步（以O(1)的时间）访问到它们。更进一步地，在末尾插入数据也可以一步完成
• 因为双向链表能直接访问前端和末端的结点，所以在两端插入的效率都为O(1)，在两端删除的效率也为 O(1)。由于在末尾插入和在开头删除都能在 O(1)的时间内完成，因此拿双向链表作为队列的底层数据结构就最好不过了。

第12章 让一切操作都更快的二叉树

• 2025/04/18 发表想法：这里完全是根据前文的铺垫来引出了二叉树的数据结构，非常直观明了！

既要保持顺序，又要快速查找、插入和删除，看来有序数组和散列表都不行。那还有什么数据结构可以选择？

看看二叉树吧。

12.1 二叉树

• 树也是基于结点的数据结构，但树里面的每个结点，可以含有多个链分别指向其他多个结点。
• [插图]
• 最上面的那一结点（此例中的“j”）被称为根。
• 此例中，“j”是“m”和“b”的父结点，反过来，“m”和“b”是“j”的子结点。“m”又是“q”和“z”的父结点，“q”和“z”是“m”的子结点。
• 树可以分层。此例中的树有3层。
• 二叉树是一种遵守以下规则的树。每个结点的子结点数量可为0、1、2。如果有两个子结点，则其中一个子结点的值必须小于父结点，另一个子结点的值必须大于父结点。
• 小于父结点的子结点用左箭头来表示，大于父结点的子结点则用右箭头来表示。

12.2 查找

• 二叉树的查找算法先从根结点开始。(1) 检视该结点的值。(2) 如果正是所要找的值，太好了！(3) 如果要找的值小于当前结点的值，则在该结点的左子树查找。(4) 如果要找的值大于当前结点的值，则在该结点的右子树查找。
• 二叉树查找的时间复杂度是O(log N)。因为每行进一步，我们就把剩余的结点排除了一半（不过很快就能看到，只在最好情况下，即理想的平衡二叉树才有这样的效率）。

12.3 插入

• 要探索二叉树插入的算法，我们还是从一个实例入手吧。假设现在要往刚才的树里插入45。首先要做的就是找出45应该被链接到哪个结点上。先从根开始找起。[插图]因为45小于50，所以我们转到左子结点上。
• 在这个例子里，插入花了5步，包括4步查找和1步插入。插入这1步总是发生在查找之后，所以总共log N + 1步。按照忽略常数的大O来说，就是O(log N)步。
• 有序数组查找需要O(log N)，插入需要O(N)，而二叉树都是只要O(logN)。
• 2025/04/18 发表想法：树结构退化为链表，时间复杂度退化为on

只有用随意打乱的数据创建出来的树才有可能是比较平衡的。要是插入的都是已排序的数据，那么这棵树就失衡了，它用起来也会比较低效。比如说，按顺序插入1、2、3、4、5的话，得出的树就会是这样。

• 因此，假若你要用有序数组里的数据来创建二叉树，最好先把数据洗乱。在完全失衡的最坏情况下，二叉树的查找需要O(N)。在理想平衡的最好情况下，则是O(log N)。

12.4 删除

• 如果要删除的结点没有子结点，那直接删掉它就好。如果要删除的结点有一个子结点，那删掉它之后，还要将子结点填到被删除结点的位置上。
• 如果要删除的结点有两个子结点，则将该结点替换成其后继结点。一个结点的后继结点，就是所有比被删除结点大的子结点中，最小的那个。
• 那计算机是怎么找出后继结点的呢？这是有算法可循的。跳到被删除结点的右子结点，然后一路只往左子结点上跳，直到没有左子结点为止，则所停留的结点就是被删除节点的后继结点。
• 如果后继结点带有右子结点，则在后继结点填补被删除结点以后，用此右子结点替代后继结点的父节点的左子结点。
• 以下为二叉树的删除算法的所有规则。如果要删除的结点没有子结点，那直接删掉它就好。如果要删除的结点有一个子结点，那删掉它之后，还要将子结点填到被删除结点的位置上。如果要删除的结点有两个子结点，则将该结点替换成其后继结点。一个结点的后继结点，就是所有比被删除结点大的子结点中，最小的那个。如果后继结点带有右子结点，则在后继结点填补被删除结点以后，用此右子结点替代后继结点的父节点的左子结点。
• 跟查找和插入一样，平均情况下二叉树的删除效率也是O(log N)。因为删除包括一次查找，以及少量额外的步骤去处理悬空的子结点。有序数组的删除则由于需要左移元素去填补被删除元素产生的空隙，最终导致O(N)的时间复杂度。

12.5 二叉树实战

• 二叉树在查找、插入和删除上引以为傲的O(log N)效率，使其成为了存储和修改有序数据的一大利器。
• 书名的搜索和更新，可以按我们之前介绍的二叉树查找、插入和删除来解决。但依照字母序打印书名该怎么做呢？首先，我们得学会如何访问树上的所有结点。访问数据结构中所有元素的过程，叫作遍历数据结构。
• 虽然有多种方法可以遍历树，但对于这个要求字母序打印的应用，我们采用中序遍历。
• (1) 如果此结点有左子结点，则在左子结点上调用自身（traverse）。(2) 访问此结点（对于书目应用来说，就是打印结点的值）。(3) 如果此结点有右子结点，则在右子结点上调用自身（traverse）。若当前结点没有子结点，则意味着该递归算法到达了基准情形，这时我们无须再调用traverse，只需打印结点中的书名就行了。

12.6 总结

• 二叉树是一种强大的基于结点的数据结构，它既能维持元素的顺序，又能快速地查找、插入和删除。
• 树形的数据结构除了二叉树以外还有很多种，包括堆、B树、红黑树、2-3-4树等。它们也各有自己适用的场景。

第13章 连接万物的图

13.1 图

• 图是一种善于处理关系型数据的数据结构，使用它可以很轻松地表示数据之间是如何关联的。
• 按照图的术语来说，每个结点都是一个顶点，每条线段都是一条边。当两个顶点通过一条边联系在一起时，我们会说这两个顶点是相邻的。
• 图的实现形式有很多，最简单的方法之一就是用散列表（参见第7章）。
• [插图]
• Alice关注了Bob和Cynthia，但没有人关注Alice。Bob和Cynthia互相关注。
• Twitter中的关系是单向的，我们也在图中用箭头表示了其方向，因此它的图是有向图。Facebook中的关系则是相互的，我们只画成了普通的线段，它的图是无向图。
• 尽管只用散列表也可以实现一个图，但是以面向对象的方法来写会更加健壮。

13.2 广度优先搜索

• LinkedIn的一个有名的功能就是，你除了能够看到自己直接添加的联系人，还可以发掘你的二度、三度联系人。
• Alice能直接联系到Bob, Bob能直接联系到Cynthia。但Alice无法直接联系到Cynthia。由于她们之间的联系要经过Bob，因此Cynthia是Alice的二度联系人。
• 图有两种经典的遍历方式：广度优先搜索和深度优先搜索。
• 广度优先搜索算法需要用队列（参见第8章）来记录后续要处理哪些顶点。该队列最初只含有起步的顶点（对本例来说，就是Alice）。
• 因为Irena没有顶点需要访问，而且队列空了，所以算法结束！
• 以广度优先搜索的方式展示一个人的关系网里所有的名字。
• 将算法的步骤分为两类之后，我们可以看出图的广度优先搜索的效率。让顶点出队，将其设为当前顶点。访问每个顶点的邻接点。
• 我们会访问Bob所有的邻接点，其中不但有Fred，还有Alice！尽管她曾被访问过，不用再入队，但访问她还是增加了一次each循环。
• 访问邻接点所用的步数，是图中边数的两倍。因为一条边连接着两个顶点，对于每个顶点，我们都要访问其所有邻接点。所以每条边都会被使用两次。
• 2025/04/18 发表想法：vertical+edge。

因为广度优先搜索有O(V)次出队，还有O(E)次访问，所以我们说它的效率为O(V + E)。

• 因为广度优先搜索有O(V)次出队，还有O(E)次访问，所以我们说它的效率为O(V + E)。

13.3 图数据库

• 因为图擅长处理关系信息，所以有些数据库就以图的形式来存储数据。
• 这种信息也可以用关系型数据库来存储。那得需要两张表——一张保存个人信息，另一张保存朋友关系。
• 那我们就来看看以关系型数据库为后端的应用会怎样执行她的请求。
• 首先，我们得找出User表中Cindy的id。
• 找出Friendships表中所有user_id为3的行。
• 有了id列表之后，我们还得回Users表找出这些id对应的行。计算机从Users表查找一行的速度大概是O(log N)。因为数据库中的行会按照id的顺序来维护，所以我们可以用二分查找来找出id对应的行。（以上解释只适用于部分关系型数据库，其他关系型数据库可能有不同做法。）
• 推广开来，若有M个朋友，那么提取他们个人信息的效率就为O(M log N)。
• 相比之下，后端为图数据库时，一旦在数据库中定位到Cindy，那么只需一步就能查到她任一朋友的信息。因为数据库中的每个顶点已经包含了该用户的所有信息，所以你只需遍历那些连接Cindy与朋友的边即可。
• 用图数据库的话，有N个朋友就需要O(N)步去获取他们的数据。与关系型数据库的O(M log N)相比，确实是极大的效率提升。
• Neo4j是开源的图数据库中比较受欢迎的一个。我建议你上它的官网去了解更多关于图数据库的知识。其他开源的图数据库还有ArangoDB和Apache Giraph。

13.4 加权图

• 还有一种图叫作加权图。它跟普通的图类似，但边上带有信息。
• 加权图可以是有方向的。以下图为例，尽管从Dallas飞到Toronto只要138美元，但从Toronto飞到Dallas要216美元。
• 要往图里加上权重，得稍微更改一下我们的Ruby代码。具体来说，我们要把表示邻接点的数组换成散列表。对于上图来说，一个顶点就是一个City类的对象
• 把表示邻接点的数组换成散列表

dallas=City.new("Dallas")
toronto=City.new("Toronto")
dallas.add_route(toronto, 138)
toronto.add_route(dallas, 216)

• 我们可以借助加权图来解决最短路径问题。
• 这就是一种最短路径问题：如何以最低的价钱从Atlanta飞往El Paso。

13.5 Dijkstra算法

• 解决最短路径问题的算法有好几种，其中一种有趣的算法是由Edsger Dijkstra（念为“dike’ struh”）于1959年发现的。该算法也很自然地被称为Dijkstra算法。
• 2025/04/18 发表想法：从广度优先搜索推广到带有双向权重的图的最短路径算法。

(1) 以起步的顶点为当前顶点。
(2) 检查当前顶点的所有邻接点，计算起点到所有已知顶点的权重，并记录下来。
(3) 从未访问过（未曾作为当前顶点）的邻接点中，选取一个起点能到达的总权重最小的顶点，作为下一个当前顶点。
(4) 重复前3步，直至图中所有顶点都被访问过。

• 既然从当前顶点（Boston）出发的航线都已探索过了，就得找下一个从起点Atlanta所能到达的最便宜的未访点了。
• 现在所有顶点都访问过了，这就意味着Atlanta到其他城市的所有路径都已发掘。
• 我们先创建一个代表城市的Ruby类。一个城市就是图上的一个结点，它记有自己的名字以及可到达的城市。
• 然后用add_route来建立城市间的航线。

class City
  attr_accessor :name, :routes

  def initialize(name)
    @name = name
    # 把表示邻接点的数组换成散列表
    @routes = {}
    # 如果此城市是Atlanta，则散列表应包含：
    # {boston => 100, denver => 160}
  end

  def add_route(city, price_info)
    @routes[city] = price_info
  end
end

atlanta=City.new("Atlanta")
boston=City.new("Boston")
chicago=City.new("Chicago")
denver=City.new("Denver")
el_paso=City.new("El Paso")
atlanta.add_route(boston, 100)
atlanta.add_route(denver, 160)
boston.add_route(chicago, 120)
boston.add_route(denver, 180)
chicago.add_route(el_paso, 80)
denver.add_route(chicago, 40)
denver.add_route(el_paso, 140)

def dijkstra(starting_city, other_cities)
  # 散列表routes_from_city用来保存从给定城市到其他所有城市的价格
  # 以及途经的城市
  routes_from_city = {}

  # 它的格式如下：
  # {终点城市 => [价格，到达终点城市前所要经过的那个城市]}
  # 以上图为例，此散列表最后会是：
  # {atlanta => [0, nil], boston => [100, atlanta], chicago => [200, denver],
  # denver => [160, atlanta], el_paso => [280, chicago]}
  # 从起点城市到起点城市是免费的
  routes_from_city[starting_city] = [0, nil]

  # 初始化该散列表时，因为去往所有其他城市的花费都未知，所以先设为无限
  other_cities.each do |city|
    routes_from_city[city] = [Float::INFINITY, nil]
  end

  # 以上图为例，此散列表起初会是：
  # {atlanta => [0, nil], boston => [Float::INFINITY, nil],
  # chicago => [Float::INFINITY, nil],
  # denver => [Float::INFINITY, nil], el_paso => [Float::INFINITY, nil]}
  
  # 已访问的城市记录在这个数组里
  visited_cities = []

  # 一开始先访问起点城市，将current_city设为它
  current_city = starting_city

  # 进入算法的核心逻辑，循环访问每个城市
  while current_city
    # 正式访问当前城市
    visited_cities << current_city

    # 检查从当前城市出发的每条航线
    current_city.routes.each do |city, price_info|
      # 如果起点城市到其他城市的价格比routes_from_city所记录的更低，
      # 则更新记录
      if routes_from_city[city][0] > price_info + routes_from_city[current_city][0]
        routes_from_city[city] = [
          price_info + routes_from_city[current_city][0], current_city
        ]
      end
    end

    # 决定下一个要访问的城市
    current_city = nil
    cheapest_route_from_current_city = Float::INFINITY

    # 检查所有已记录的路线
    routes_from_city.each do |city, price_info|
      # 在未访问的城市中找出最便宜的那个，
      # 设为下一个要访问的城市
      if price_info[0] < cheapest_route_from_current_city && !visited_cities.include?(city)
        cheapest_route_from_current_city = price_info[0]
        current_city = city
      end
    end
  end

  return routes_from_city
end

• 虽然这个例子是找出最便宜的航线，但其解决方法也适用于地图软件和GPS技术。如果边上的权重不是表示价格，而是表示行车用时，那就可以用Dijkstra算法来确定从一个城市去另一个城市应该走哪条路线。

13.6 总结

• 我们知道了图是处理关系型数据的强大工具，它除了能让代码跑得更快，还能帮忙解决一些复杂的问题。
• 性能的衡量方法不止这些。在某些情况下，还有比速度更重要的东西，比如我们可能更关心一种数据结构或算法会消耗多少内存。

第14章 对付空间限制

• 当内存有限时，空间复杂度便会成为选择算法的一个重要的参考因素。
• 既省时又省内存的算法当然是最理想的。但有些情况下我们却只能二者选其一

14.1 描述空间复杂度的大O记法

• 我们也可以用大O来描述一个算法需要多少空间：当所处理的数据有N个元素时,该算法还需额外消耗多少元素大小的内存空间。
• 等到该函数结束的时候，内存里会存在两个数组，一个是array，它里面是[“amy”, “bob”,“cindy”, “derek”]；另一个是newArray，它里面是[“AMY”, “BOB”, “CINDY”, “DEREK”]。
• 在这第二个版本里，我们没有创建任何新的变量或新的数组，也确实没有消耗额外的内存空间。我们只是变动了原array里的每个字符串，将它们逐一换成大写。最后返回这个修改过的array。
• 时间复杂度的O(1)意味着一个算法无论处理多少数据，其速度恒定。相似地，空间复杂度的O(1)则意味着一个算法无论处理多少数据，其消耗的内存恒定。
• 值得一再强调的是，空间复杂度是根据额外需要的内存空间（也叫辅助空间）来算的，也就是说原本的数据不纳入计算。
• 有些参考书在计算空间复杂度时是连原始输入也一起算的，那没问题。但此处我们不计算它，当你在其他地方看到某一算法的空间复杂度的描述时，最好留意一下它是否计算原始输入。

14.2 时间和空间之间的权衡

• 第一版所用的内存更少，但跑得更慢，第二版虽跑得快但用的内存更多。
• 如果你想要程序跑得超级快，而且你的内存十分充足，那么用第二版会比较好。但如果你不看重速度，而且你的程序是跑在需要谨慎使用内存的嵌入式系统上，那你应该选择第一版。

14.3 写在最后的话

• 你懂得了数据结构和算法的分析，这对代码的速度、内存占用，甚至其可读性都有着重大影响。
• 你明白了计算包含各种细节，尽管大O之类的理论会建议你哪种做法更好，但若考虑其他因素，你可能会做出不同的选择。机器对内存的管理方式和编程语言的底层实现都会影响程序的性能，甚至有时你以为是最高效的做法也可能会随着外部环境的变化而变得低效。
• 很多看似复杂、深奥的事物，其实都是由你所掌握的简单概念构筑而成的。不要因为某些资料没解释到位，就以为它很困难而被吓退，你一定能找到更详尽的解释资料。