fleury算法代码怎么写

大家好，我是何老师。今天呢，我们来看一道 gsp 五集中出现的一个有关于规定排序算法的一个题目， 规定排序是咱们比较常见的一个排序，十大排序中的经典排序，它的这个代码和这个复杂度咱们应该都比较熟悉。 ok， 那 我们来看一下它的考点是什么？先简单浏览一下它的代码，看有没有问题。 ok， 比较经典的写法啊，没什么问题。对于长度为 n 的 数组 ar 调用这个函数 much salt， 在 排序过程中， much 函数的调用递归调用次数大约是 a o， e b o n c log n d n b 的 log n。 有 的同学呢，比较急性，子题目读完以后直接秒选 d， 为什么呢？因为 n 倍的 log n 就是 规定的总的时间复杂度。 但是同学呀，你看清楚题目，人家问的是时间复杂度吗？人家问的是函数的递归调用次数啊，并不是复杂度， 如果是复杂度的话，那你就对了，但并不是啊，所以呢，我们首先要把 d 排除掉，那么它的调用次数我们应该怎么去算呢？首先呢，我们要给他建立一个模型，那么规定应该属于哪个模型呢？ 规定属于我们分制算法对不对？那么分制呢，是不是应该属于二叉数模型里面？所以呢，我们可以套二叉数的模型去算，它 就是很简单，就是如果我们把它想象成一棵二叉树的话，那么它只有一个问题，就是这棵树有多少个非叶子节点， 它的非叶子节点的数量就是它的地规调用次数。为什么呢？比如说我们一个负节点，它是由两个子节点构成的， 左边和右边嘛，它需要调用默尺实现合并，所以每合并一次呢，都会产生一个非叶子节点， 所以呢，它的总的调用次数就等于什么？就等于非叶子节点数，其实也就是 n 减一呗。 为什么是 n 减一呢？有的同学可能想不明白啊，我们简单来画一个 r 叉数啊，比如说我们有 a、 b、 c、 d 四个节点啊，首先我们的起始啊，我们可以设 c 和 d， c 和 d 进行默尺，会形成 c、 d， 再搞一个 a 和 b， ab 进行默尺，得到 ab， 然后 ab 和 cd 再默尺一下，会得到 abcd。 那 么这个儿差数里面有几个非叶子节点数了，那我们简单来看，算一下就知道了，这不是一个吗？哎，这是第二个呗， 还有一个就是 c d 呗，所以呢，是不是三个？是不是就是 n 减一？你再想想，是不是默扯了三次，这是一次，这是一次，这是一次。 所以呢，看到题目的时候，先不要着急嘛，先看看人家问什么。其实这道题问的非常简单啊，有的同学可能还不知道这个规定它的复杂度是 n b 的 log n 啊，但其实呢，你简单的画一个差数，推算一下就能把它算出来啊，非常的简单啊。 好，我们来看一下它的这个选项， a 选项是 o 一， o 一， 你蒙也不可能蒙 o 一 啊，对吧？它有地规呢，怎么哪来的 o 一 呢？而且随着它的 n 的 一个增加呢，它肯定不可能是一啊，肯定会调用次数越来越多呀，对吧？然后 log n， log n 是 数的高度啊，对不对？多少层，它调用的是次数啊，就是它的节点数永远是超过的这个 log n 的， 然后 d 我 们刚讲了是总的时间复杂度，所以呢应该选择 o n。 这道题呢，主要是考察我们对这个规定的一个理解啊，如果你的规定掌握的非常熟练的话，其实这道题呢，就可以用公式套进去就秒了啊，就是 n 减一是吧？直接就秒掉了。好，这道题呢，就是规定排序的一道题目。

今天介绍一款非常简洁好用的格式化算法学习工具，在 github 上收获了近两万 star。 该工具最左边为目录区， 你可以在这里选择算法和计算机语言窗口，最中间为算法的动态演示区域和输出日制右侧实时显示程序当前执行到哪一行。右边上面都是工具栏，在这里你可以选择播放或者暂停，甚至还有播放速度，可以说非常简洁直观了，而且也支持。

算法大题毫无头绪，打算放掉的同学别急，你们的临时抱佛教同盟大军来救你了。大题基本上是这样的，三问难度递增，我们拿个六七分还是很有机会的。第一问， 思路分必须抢，不管你会不会写代码，只要你能粘到关键点，三四分就到手了。第二问，我们只搭一个万能的核心框架，两到三分的空壳分就到手了。这是一个参考，但是这个吃相有点难看， 被老师识破了，心情不好给个一分，你可以更聪明，把背过的代码写进去，三五行六七分就到手了。第三问，直接记，别浪费时间了孩子们。