作者 谢恩铭，"大众年夜众号「程序员同盟」。
转载请注明出处。
原文：https://www.jianshu.com/p/060ef52580af
经由 数据构造和算法 | 第一部分第三课：算法繁芜度（上） 和 数据构造和算法 | 第一部分第四课：算法繁芜度（下） ，我们讲完了算法繁芜度，是时候来做点实践的练习，巩固一下所学知识点了。
算法的繁芜度是个不错的知识点，但是它与我们这门算法的课程有什么关系呢？我们逐步来看。
算法学（Algorithmics）是设计和研究算法的科学，它的历史可比打算机科学的历史久远多了，但本日年法学却险些全由打算机科学家实践。
算法学是一个非常广泛的领域，须要不少数学知识。当然了，并非所有打算机科学家都须要成为天才的算法学家。从算法的角度来看，大多数程序员面临的问题实际上非常大略。
但我们有时须要实现一些更繁芜的东西。在这种情形下，算法方面的基本知识就会显得非常有用。我们并不哀求你发明一种革命性的新算法并给出其繁芜度的详细证明，但为了能够准确地利用那些在网络上或软件库中找到的算法，还是有必要接管一下“根本培训”的。
懂算法会让你更有效率，能够更好地理解你所要办理的问题，也不会写出不规范的代码：有一些代码只管可以正常运行，但从算法的角度来看却是不合理的。一个履历不丰富的程序员可能会直策应用这些不合格的算法（他会想：“代码能运行，以是该当没什么问题”），但你由于懂算法，就能很快创造代码的问题，并改写出一个精良得多的版本。
听我说了这些，你可能有点跃跃欲试了。下面是两个大略的对付算法繁芜度的研究题，它们可以让你更准确地理解算法繁芜度的浸染。
2. 探求最大和最小的元素问题 1：有一个正整数列表，我们想要找到列表中最大的整数。
这个问题的经典解法如下：遍历此列表，并一贯保存迄今为止创造的最大元素，称其为“当前最大值”。
我们可以将此算法描述为：
一开始，“当前最大值”即是 0。我们用列表中每一个元素去和“当前最大值”做比较，如果当前遍历到的元素比“当前最大值”更大，则将“当前最大值”设为当前元素的值。在遍历完全个列表后，“当前最大值”就真的“实至名归”了。
下面我们给出此算法的一种实现，是用“天下上最好的编程措辞” PHP 来实现的（当然，你也可以用其他编程措辞来实现）：
<?phpfunctionmax($list){$current_max=0;foreach($listas$item)if($item>$current_max)$current_max=$item;return$current_max;}?>
我们可以快速验证此算法是精确的：我们只须要确认在此算法实行时，“当前最大值”总是即是到目前为止所遍历到的列表元素里最大的那个值。
我们也把稳到此算法是会“结束”的，它不会陷入无限循环：此算法遍历完全个列表，然后停滞。这看起来像一个不主要的细节，但实际上有一些编程措辞里是可以表示无限多元素的列表的：在这种情形下，我们的算法是禁绝确的。
现在让我们研究此算法的繁芜度。我们要考虑哪些操作呢？显然，大部分事情都在于将当前元素与“当前最大值”进行比较（毕竟，“当前最大值” current_max 的初始化（初始化为 0）并不占多少运行韶光），因此我们打算“比较操作”的次数，将其作为此算法的操作数。
算法的实行韶光取决于哪些参数呢？可以想见，实行韶光并不依赖于列表中每个元素的值（在此，我们假设两个整数的比较韶光是恒定的，不论它们的值是多少）。因此，我们用元素列表的长度 N 来量化输入。
对付一个包含 N 个元素的列表，我们要进行 N 次比较：每个元素都与“当前最大值”进行一次比较。因此，算法的韶光繁芜度是 O(N)：它的实行韶光是呈线性的，与列表的元素数目 N 成正比。
那么，此算法的空间繁芜度是多少呢？此算法利用了一个列表，里面的元素占用了一定的内存空间。但是，这个列表在我们查找其最大元素之前就已经存在了，它所占用的内存空间并不是由我们的算法分配的，因此我们说此列表的元素数目 N 并不会被考虑到算法的空间繁芜度的打算中，我们只考虑由我们的算法直接申请的内存。
而我们的算法直接申请的内存空间险些可以忽略不计，由于最多便是占用了一个临时变量（current_max），用以存储“当前最大值”。因此，我们的算法所占用的内存空间不依赖于列表的长度： （我们将空间繁芜度记为 O(1)，表示它不依赖于 N）。
对付我们的算法，现在只剩下一个小细节要把稳了：如果我们的列表是空的，那么返回的最大值将是 0。要说“一个空的列表的最大值是 0” 显然不一定是精确的：在某些情形下，如果列表是空的，最好返回一个缺点。
因此我们可以改进一下我们的算法：我们不再为“当前最大值”赋初值为 0，而因此列表的第一个元素（如果该列表为空，则返回一个缺点）作为“当前最大值”的初始值。然后，我们从第二个元素开始比较。
经由改进后的算法实行 N-1 次比较（由于我们不必将第一个元素与它自己进行比较）。不过，这并没有改变算法的韶光繁芜度：N 和 N-1 之间的韶光差并不依赖于 N，它是恒定的，因此我们可以忽略它：两种算法具有相同的韶光繁芜度，它们都是韶光线性的（韶光繁芜度是 O(N) ）。
末了，我们把稳到第二个算法也适用于负数（如果列表的所有元素都是负数，第一个算法会返回 0，这显然禁绝确）。因此改良后的第二个算法更通用，也更好。
当然了，查找列表中最小值的算法和查找最大值是类似的，我们就不赘述了。
3. 探求不重复的元素现在我们来看第 2 个问题。
问题 2：有一个列表 1，个中包含重复项（多次涌现的元素）：我们想要构建一个包含与列表 1 相同元素的列表 2，但是列表 2 中每个元素只重复涌现一次。
例如，列表 1 里有以下元素：
AABCDBCA
则列表 2 将包含以下元素：
ABCD
你想到办理这个问题的算法了吗？在阅读我的办理方案之前，请自己思考一下。
我的办理方案我的算法如下：
对付给定的包含重复元素的列表 L，我们要构建一个新的列表 U（取英语 Unique（“独一无二的”）的第一个字母），列表 U 一开始是空的，我们须要往里面添补元素。我们遍历列表 L，对付列表 L 中的每一个元素，我们确认一下它是否存在于列表 U 中（可以用与之前的查找最大元素类似的算法，毕竟便是逐一比较元素嘛）。如果列表 L 中遍历到的元素还不在列表 U 中，就将这个元素添加进列表 U 中；如果已经存在于列表 U 中，就不添加。遍历完列表 L 后，列表 U 中就拥有了和列表 L 相同的元素，只是这些元素都是不重复涌现的。
练习： 利用你喜好的编程措辞来实现上述从列表中提取不重复元素的算法。
繁芜度这个算法的繁芜度是多少？如果你充分理解了之前查找列表最大值的算法的繁芜度的打算，那么这对你来说该当很大略。
对付给定列表 L 中的每个元素，我们都会实行遍历列表 U 的操作，因此实行的操作数与列表 U 包含的元素数目有关。
但问题是：列表 U 的大小在遍历给定列表 L 的过程中会发生变革，由于我们会添加元素进列表 U。当我们遍历到列表 L 中的第一个元素时，列表 U 还是空的（因此我们不实行任何比较操作）；当我们遍历到列表 L 的第二个元素时，列表 U 有 1 个元素，以是我们要再实行一个比较操作。
但是当我们遍历到列表 L 中的第三个元素时，我们就变得不是那么肯定了：如果列表 L 中的前两个元素是不相同的，它们都被添加到 U 中，在这种情形下我们要实行 2 次比较操作（将列表 L 中的第三个元素分别与列表 U 中的两个元素作比较）；如果前两个元素是相同的，那么列表 L 中的第二个元素就没有被添加到列表 U 中，只实行 1 次比较操作。
正如我们的课程里已经说过的，繁芜度的打算须要考虑在“最坏的情形”（worst case）下：也便是实行的操作数目最多时的繁芜度。因此，我们将认为给定列表 L 的所有元素都是不相同的。
在“最坏的情形”下，我们将给定列表 L 的所有元素逐一添加进列表 U 中。假设给定列表 L 一共有 N 个元素，在遍历到给定列表 L 的第 N 个元素时，我们已经向列表 U 添加了 (N-1) 个元素了，因此这时要做 (N-1) 次比较操作。
以是我们统共要做的比较操作数是 0 + 1 + 2 + … + (N-1) 。开始时的操作数少，越到后面做的操作越多（有点像人生，出生时任务比较少，逐步地任务越来越大，要处理的事情也越来越多，不过也解释你在发展，毕竟“能者多劳”）。
上面这一串数字相加，得到的总操作数是 N (N - 1) / 2（这个不难，是数学里面的等差数列求和公式），由于我们在打算繁芜度时考虑的是 N 很大的情形，上面的结果可以约即是 N N / 2，即 N2 / 2 个操作。
因此，我们的算法具有 O(N2) 的韶光繁芜度（我们去除了常数因子 1/2）。我们也可以称 O(N2) 为“二次/平方”的繁芜度（正如我们称 O(N) 具有“线性”的繁芜度）。
与之前那个查找最大元素的算法比起来，现在这个算法除了速率较慢（韶光繁芜度较高）之外，还具有更高的空间繁芜度：我们构建了一个最初不存在的列表 U（因此申请了内存空间）。
在最坏的情形下，列表 U 还具有与给定列表 L 一样多的元素：因此将为 N 个元素分配空间，这使得空间繁芜度为 O(N)。之前查找最大元素的算法的空间繁芜度是恒定的（O(1)），但现在这个算法的空间繁芜度却是线性的（O(N)）。
该算法只须要比较元素，因此被操作的元素并不一定假如整数：我们可以用相同的算法来肃清单词列表中重复的单词，重复的浮点数，等等。因此，许多算法是与利用的元素的详细类型无关的。
4. 探求不重复的元素：另一种方法探求不重复的元素，实在还有另一种算法（聪明如你可能也想到了）：我们可以先对给定列表 L 中的元素进行排序，使得所有重复的元素都相邻，这样打消重复元素将变得很大略。
比如给定列表 L 初始是这样的：
AABCDBCA
我们可以在构建列表 U 前，先对列表 L 进行排序，使其变成下面这样：
AAABBCCD
这样，我们之后构建列表 U 的算法就大略了。
算法如下：只需遍历排序后的列表 L，并记住最近一次遍历到的那个元素。如果当前元素与前一个元素相同，则这个元素是重复的，就不要把它包含在不重复元素的列表 U 中。
如果重复的元素彼此不相邻，则上述算法不再有效。因此我们必须先对列表进行排序。
这个新的算法的韶光繁芜度是什么？肃清重复是在列表的单次遍历中完成的，因此是线性的（ O(N)）。但由于我们必须先对列表进行排序，因此第一步排序的操作也必须被考虑进这种新算法的总繁芜度中。
当然了，在这里提到列表的排序还轻微有一些太早了，由于我们在之后的课程里才会讲到排序算法。
只管目前我们还没有学习排序算法和它们的繁芜度，但我还是想说一下这个新算法的繁芜度问题。
事实证明，这种算法的繁芜度取决于排序的繁芜度：由于，排序基本上会实行 N2 个操作，这远远超过我们之后的构建列表 U 时的 N 个操作，以是整体繁芜度是 O(N2)。
然而，也存在更高真个排序算法，虽然仍旧实行多于 N 个操作，但比 N2 要少得多。
我们将在之后的课程里学习排序算法，目前你只须要知道这个多了一步排序的新算法比旧算法更有效，也更“高等”。
“在列表中搜索指定元素”与“找出列表中最大/小值的元素”是非常相似的算法，都是线性韶光的（算法的韶光繁芜度是 O(N)），空间繁芜度都是 O(1)。
肃清列表中的重复元素的算法更繁芜一些，由于最大略的算法在韶光上具有平方的韶光繁芜度（O(N2)），其空间繁芜度具有线性（O(N)）。
我希望这些更详细的研究能让你确信算法学和算法繁芜度还是很有用的。现在你也该当已经习气“算法”，“韶光繁芜度”，“空间繁芜度”这些基本观点了。
下一课开始，我们要学习数据构造了，这样我们就能把数据构造和算法相结合并交融贯通了，毕竟这一对“活宝”是和衷共济的。
5. 第一部分第六课预报本日的课就到这里，一起加油吧！
下一课：数据构造和算法 | 第一部分第六课：数据构造之数组和链表（上）
我是 谢恩铭，公众号「程序员同盟」号主，慕课网精英讲师 Oscar 老师，终生学习者。热爱生活，喜好拍浮，略懂烹饪。人生格言：「向着标杆直跑」
