算法图解读后笔记

1.2.2 运行时间：

如果列表包含100个数字，最多需要猜100次。如果列表包含40亿个数字，最 多需要猜40亿次。换言之，最多需要猜测的次数与列表长度相同，这被称为线性 时间（linear time）。

二分查找则不同。如果列表包含100个元素，最多要猜7次；如果列表包含40亿个数字，最多 需猜32次。厉害吧？二分查找的运行时间为对数时间（或log时间）。

仅知道算法 需要多长时间才能运行完毕还不够，还需知道运行时间如何随列表增长 而增加。这正是大O表示法的用武之地。

大O表示法指出了算法有多快。例如，假设列表包含n个元素。简 单查找需要检查每个元素，因此需要执行n次操作。使用大O表示法， 这个运行时间为O(n)。单位秒呢？没有——大O表示法指的并非以秒为单位的速度。大O表示法 让你能够比较操作数，它指出了算法运行时间的增速。

再来看一个例子。为检查长度为n的列表，二分查找需要执行log n次操作。使用大O表示法， 这个运行时间怎么表示呢？O(log n)。一般而言，大O表示法像下面这样。

1.3.3 大 O 表示法指出了最糟情况下的运行时间 假设你使用简单查找在电话簿中找人。你知道，简单查找的运行时间为O(n)，这意味着在最 糟情况下，必须查看电话簿中的每个条目。如果要查找的是Adit——电话簿中的第一个人，一次 就能找到，无需查看每个条目。考虑到一次就找到了Adit，请问这种算法的运行时间是O(n)还是 O(1)呢？ 简单查找的运行时间总是为O(n)。查找Adit时，一次就找到了，这是最佳的情形，但大O表 示法说的是最糟的情形。因此，你可以说，在最糟情况下，必须查看电话簿中的每个条目，对应 的运行时间为O(n)。这是一个保证——你知道简单查找的运行时间不可能超过O(n)

1.3.4 一些常见的大 O 运行时间 

下面按从快到慢的顺序列出了你经常会遇到的5种大O运行时间。 

 O(log n)，也叫对数时间，这样的算法包括二分查找。 

 O(n)，也叫线性时间，这样的算法包括简单查找。 

 O(n * log n)，这样的算法包括第4章将介绍的快速排序——一种速度较快的排序算法。 

 O(n2 )，这样的算法包括第2章将介绍的选择排序——一种速度较慢的排序算法。 

 O(n!)，这样的算法包括接下来将介绍的旅行商问题的解决方案——一种非常慢的算法。

假设你要绘制一个包含16格的网格，且有5种不同的算法可供选择，这些算法的运行时间如 上所示。如果你选择第一种算法，绘制该网格所需的操作数将为4（log 16 = 4）。假设你每秒可执 行10次操作，那么绘制该网格需要0.4秒。如果要绘制一个包含1024格的网格呢？这需要执行10 （log 1024 = 10）次操作，换言之，绘制这样的网格需要1秒。这是使用第一种算法的情况。 第二种算法更慢，其运行时间为O(n)。即要绘制16个格子，需要执行16次操作；要绘制1024 个格子，需要执行1024次操作。执行这些操作需要多少秒呢？

获得的主要启示如下。

 算法的速度指的并非时间，而是操作数的增速。 

 谈论算法的速度时，我们说的是随着输入的增加，其运行时间将以什么样的速度增加。 

 算法的运行时间用大O表示法表示。 

 O(log n)比O(n)快，当需要搜索的元素越多时，前者比后者快得越多。

推而广之，涉及n个城市时，需要执行n!（n的阶乘）次操作才能计算出结果。因此运行时间 为O(n!)，即阶乘时间。

链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起。

在链表中，元素并非靠在一起的，你无法迅速计算出第五个元素的内存 地址，而必须先访问第一个元素以获取第二个元素的地址，再访问第二个元素以获取第三个元素 的地址，以此类推，直到访问第五个元素。

有两 种访问方式：随机访问和顺序访问。顺序访问意味着从第一个元素开始逐个地读取元素。链表只 能顺序访问：要读取链表的第十个元素，得先读取前九个元素，并沿链接找到第十个元素。随机 访问意味着可直接跳到第十个元素。本书经常说数组的读取速度更快，这是因为它们支持随机访 问。很多情况都要求能够随机访问，因此数组用得很多。

如果使用循环，程序的性能可能更高；如果使用递归，程序可能 更容易理解

每个递归函数都有两部分：基线 条件（base case）和递归条件（recursive case）。递归条件指的是函数调用自己，而基线条件则 指的是函数不再调用自己，从而避免形成无限循环。

编写涉及数组的递归函数时，基线条件通常是数组为空或只包含一个元素。陷入困境时， 请检查基线条件是不是这样的。

。解决最短 路径问题的算法被称为广度优先搜索。

广度优先搜索可回答两类问题。  第一类问题：从节点A出发，有前往节点B的路径吗？（在你的人际关系网中，有芒果销 售商吗？）  第二类问题：从节点A出发，前往节点B的哪条路径最短？（哪个芒果销售商与你的关系 最近？）