算法 自动采集列表(图片引自算法图解1.3大O表示法是什么，厉害吧？)

　　算法 自动采集列表(图片引自算法图解1.3大O表示法是什么，厉害吧？)

　　1.2.2 运行时

　　每次我介绍一种算法时，我都会讨论它的运行时间。通常，应选择最有效的算法以最小化运行时间或占用空间。

　　回到前面的二分查找。使用它可以节省多少时间？简单查找会一一检查数字，如果列表收录 100 个数字，则最多需要 100 次猜测。如果列表收录 40 亿个数字，则最多需要 40 亿次猜测。换句话说，所需的最大猜测次数与列表的长度相同，称为线性时间。二分查找不同。如果列表收录 100 个元素，则最多需要 7 次猜测；如果列表收录 40 亿个数字，则最多需要 32 次猜测。太好了，对吧？二分查找的运行时间是对数时间（或日志时间）。下表总结了我们的发现。

　　图片引自算法图

　　1.3 大 O 符号

　　大 O 表示法是一种特殊的表示法，表示算法的速度。谁在乎？在实践中，您经常不得不使用其他人编写的算法，在这种情况下，了解这些算法的速度会大有裨益。本节将介绍什么是大 O 表示法，并用它来列出一些最常见的算法运行时间。

　　1.3.1 算法的运行时间以不同的速率增加

　　Bob 将为 NASA 编写一个查找算法，该算法在火箭即将登陆月球之前启动，以帮助计算着陆点。

　　这个例子表明两种算法的运行时间表现出不同的增长率。Bob 需要决定是使用简单搜索还是二分搜索。使用的算法必须快速准确。一方面，二分查找更快。Bob 必须在 10 秒内找出着陆的位置，否则火箭会偏离轨道。另一方面，简单的查找算法更容易编写，因此不太可能出现错误。Bob 不希望在引导火箭着陆的代码中出现错误！为了万无一失，如果列表收录 100 个元素，Bob 决定计算两种算法需要多长时间。

　　假设检查一个元素需要 1ms。使用简单查找时，Bob 必须检查 100 个元素，因此完成查找需要 100ms。使用二分查找，只需要检查7个元素（log2100大约是7），所以需要7ms才能完成搜索。但是实际要搜索的列表可能收录10亿个元素，这种情况下，多长时间一个简单的搜索需要多少时间？二分搜索需要多长时间？一定要找到这两个问题的答案，然后继续阅读。

　　Bob 使用收录 10 亿个元素的列表运行二进制搜索，运行时间为 30 毫秒（log21 000 000 000 大约为 30）。他认为二进制搜索比简单搜索快大约 15 倍，因为列表有100个元素，简单查找需要100ms，二分查找需要7ms。所以，10亿个元素的列表，简单查找需要30×15 = 450ms，正好是10秒内完成查找的要求秒。Bob 决定使用简单查找。这是正确的选择吗？

　　不。事实上，鲍勃错了，而且大错特错。当列表收录 10 亿个元素时，一个简单的查找需要 10 亿毫秒，即 11 天！为什么会这样？因为二分查找和简单查找不同地加快了运行时间。

　　图片引自算法图

　　也就是说，随着元素数量的增加，二分查找不需要太多额外的时间，而简单查找则需要很多额外的时间。所以随着列表的增长，二分查找比简单查找要快得多。Bob 认为二分搜索比简单搜索快 15 倍，这是不正确的：当列表收录 10 亿个元素时，它快 3300 万倍。考虑到这一点，仅仅知道算法运行完成需要多长时间是不够的，还需要知道运行时间如何随着列表的增长而增加。这就是大 O 表示法的用武之地。

　　大 O 表示法表示算法的速度。例如，假设列表收录 n 个元素。一个简单的查找需要检查每个元素，所以它需要做 n 次操作。使用大 O 表示法，此运行时间为 O(n)。几秒钟后呢？否 - 大 O 符号不是指以秒为单位的速度。大 O 表示法允许您比较操作数，它指示算法运行的速度。

　　注意：大O表示法表示算法的增长率，记住二分法是O(logn)，后面会经常用到

　　让我们看另一个例子。要检查长度为 n 的列表，二进制搜索需要执行 log n 操作。这个运行时间如何用大 O 表示法来表示？O（登录）。一般来说，大 O 表示法如下所示。

　　图片引自算法图

　　这表示算法需要执行的操作数。它被称为大 O 表示法，因为在操作数之前有一个大 O。这听起来像是一个笑话，但这是真的！

　　让我们看一些示例，看看您是否可以确定这些算法的运行时间。

　　1.3.2 了解不同的 Big O 运行时

　　下面的例子可以在家里用纸和笔完成。假设您要绘制一个收录 16 个单元格的网格。

　　图片引自算法图

　　注意：先想一想，再看下面的答案，想一想：能不能用简单搜索和二分搜索？简单搜索就是一张一张的，两点呢？不记得我们小时候折纸的时候，是不是很快就能得到更多的方格呢？

　　图片引自算法图

　　绘制 16 个网格需要 16 个步骤。这个算法的运行时间是多少？

　　注：运行时间 O(n)=16

　　图片引自算法图

　　每次折叠时，绘制的方格数翻倍，因此您可以分 4 步“绘制”16 个方格。这个算法的运行时间是多少？请在弄清楚这两种算法的运行时间后继续阅读。

　　答案如下：算法 1 运行时间为 O(n)，算法 2 运行时间为 O(log n)。

　　1.3.3 大 O 符号表示最坏情况的运行时间

　　假设您使用简单查找在电话簿中查找人员。你知道，简单的查找运行 O(n)，这意味着在最坏的情况下，必须查看电话簿中的每个条目。如果您正在寻找 Adit - 电话簿中的第一个人，您可以找到它一次，而无需查看每个条目。考虑到Adit被找到一次，这个算法的运行时间是O(n)还是O(1)？简单搜索的运行时间总是O(n)。在寻找Adit的时候，找到一次是的, 这是最好的情况, 但大 O 表示法表示最坏的情况. 所以你可以说在最坏的情况下你必须查看电话簿中的每个条目, 这对应于 O (n) 的运行时间. 这是一个保证——你知道一个简单的查找运行时间不能超过 O(n)。

　　注意：这个概念很重要，最坏情况和平均情况，后面会有平均情况的解释

　　1.3.4 一些常见的 Big O 运行时

　　下面，按照从最快到最慢的顺序，列出了您经常会遇到的 5 个 big-O 运行时。

　　O(log n)，也称为对数时间，此类算法包括二分查找。O(n)，也称为线性时间，此类算法包括简单的查找。O(n * log n)，这样的算法包括快速排序，一种更快的排序算法，在第 4 章中描述。 O(n^2)，这样的算法包括选择排序，在第 2 章中描述，一种更慢的排序algorithm. O(n!)，这样的算法包括接下来描述的旅行商问题的解决方案——一个非常慢的算法。

　　假设您要绘制一个由 16 个单元格组成的网格，并且您有 5 种不同的算法可供选择，这些算法的运行时间如上所示。如果选择第一种算法，则绘制网格所需的操作数为 4（log 16 = 4）。假设您每秒可以执行 10 次操作，那么绘制网格将需要 0.@ > 4秒。如果要绘制一个有1024个单元格的网格呢？这需要10（log 1024 = 10）次操作，也就是说，绘制这样一个网格需要1秒。这是使用第一个算法案例.

　　第二种算法速度较慢，运行时间为 O(n)。即绘制16个网格，需要进行16次操作；要绘制 1024 个网格，需要执行 1024 次操作。执行这些操作需要多少秒？

　　图片引自算法图

　　还有其他运行时，但这 5 个是最常见的。事实上，这里的简化并没有将 big-O 运行时转换为操作数那么干净，但就目前而言，这种准确性就足够了。在您学习了一些其他算法之后，第 4 章将再次讨论 Big-O 表示法。目前，我们得到的主要启示如下。

　　1.3.5 旅行推销员

　　阅读上一节时，您可能会认为根本没有 O(n!) 算法。让我证明你错了！下面是一个需要很长时间才能运行的算法。该算法解决了计算机科学中非常有名的旅行商问题，其计算时间增加非常快，一些非常聪明的人认为没有改进的余地。

　　图片引自算法图

　　图片引自算法图

　　对于每个订单，他计算总行程并选择行程最短的路线。5 个城市，120 种不同的安排。所以解决这个问题需要5个城市的120个操作。当涉及 6 个城市时，需要执行 720 次操作（具有 720 种不同的排列）。当涉及7个城市时，需要5040次操作！

　　图片引自算法图

　　通过扩展，当涉及 n 个城市时，n! （n 的阶乘）运算需要计算结果。所以运行时间是 O(n!)，阶乘时间。除非涉及的城市数量很少，否则需要大量的操作。如果涉及的城市数量超过 100 个，则根本无法在合理的时间内计算出结果——等到你计算出结果的时候，太阳已经消失了。这个算法很烂！Opus 应该使用另一种算法，但他别无选择。这是计算机科学中尚未解决的问题之一。对于这个问题，目前还没有更快的算法，一些很聪明的人认为根本就没有更聪明的算法来解决这个问题。面对这个问题，我们所能做的就是找到一个近似的答案，更多细节请参见第 10 章。

　　最后要注意的一点是，高级读者可以学习二叉树，上一章简要介绍了二叉树。

　　注意：旅行商问题实际上是一个NP完全问题，后面会讨论

　　1.4 总结

　　提问时间思考？

　　1、假设有一个收录 258 个名称的有序列表，并且您想使用二进制搜索在其中找到一个名称。需要多少步骤才能找到它？（最=最差）

　　2、通过电话簿中的电话号码查找人员（使用大 O 表示法给出运行时间。）

　　数组、链表和选择排序的先睹为快：

　　数组和链表：两种数据结构，区别在于数组易于查找（本质：数组有索引），链表易于插入和删除（本质：链表的每个元素都会收录下一个元素的地址）

　　选择排序：8个人按照身高从高到低排列。如果是选择排序，第一次从8个人中找出最高的，第二次从7个人中找出最高的，以此类推。运算为8+7+6+...+1，如果推广到n，则为n*(n+1)/2。常量在big-O记法中被忽略，所以运行时间为O (n^2)，因为这个常数的问题，后面你可能会有疑惑，有些算法使用大O记法运行时间相同，但是大小有差异。记住这个常数问题！

　　下次更新时间：预计10月13-12日是课题组的周年纪念日。有必要向外国人报告。我会停下来几天，希望能理解。