免规则采集器列表算法(算法介绍最优算法的设计方法及分析估算-乐题库)

　　免规则采集器列表算法(算法介绍最优算法的设计方法及分析估算-乐题库)

　　算法介绍

　　算法是由解决问题所需的步骤组成的解决方案，每个步骤包括一个或多个操作。无论是在现实生活中还是在计算机中，解决同一个问题的方法可能有很多种。在这N种算法中，一定有一种执行效率最快的方法，那么这个方法就是最优算法。

　　组织：Gopher 文档：

　　算法具有五个基本特征：输入、输出、有限性、确定性和可行性。

　　进入

　　一个算法有零个或多个输出。为了表征运算对象的初始条件，所谓的零输入是指算法本身已经设定了初始条件。

　　输出

　　该算法至少有一个输出。换句话说，算法必须有一个输出。输出格式可以是打印，也可以返回一个值或多个值等，也可以显示一些提示。

　　贫穷

　　算法的执行步骤是有限的，算法的执行时间也是有限的。

　　肯定

　　算法的每一步都有明确的意义，没有歧义。

　　可行性

　　该算法是可用的，即它可以解决当前的问题。

　　算法设计要求：

　　正确性

　　对于合法输入可以满足的结果，算法可以进行非法处理，得到合理的结果。该算法对于边界数据和压力数据都能得到满意的结果。

　　可读性

　　算法应该易于阅读、理解和交流。只有你能理解他们，但其他人无法理解他们。多么好的算法啊。

　　稳健性

　　通俗地说，一个好的算法应该具有捕获/处理异常的能力。此外，该算法应该能够轻松处理测试人员的压力测试和边界值测试等困难的测试方法。

　　性价比高

　　用最少的时间和资源得到满足要求的结果，可以由（时间复杂度和空间复杂度）决定。

　　通常，算法的效率可以通过事后统计和事前分析来估计。

　　后统计方法的缺点：必须编写相应的测试程序，对硬件和运行环境的依赖性很大。算法数据相当困难。

　　预分析和估计：主要取决于问题的规模。

　　这里是时间复杂度和空间复杂度的解释。

　　时间复杂度：

　　时间复杂度是对排序数据的操作总数。反映当 n 变化时操作次数呈现什么规律。

　　公式：T(n) = O( f(n))，其中f(n)是问题规模n的函数，即进行某项操作的次数。

　　除非另有说明，我们分析的时间复杂度是指最坏的时间复杂度。

　　空间复杂度：

　　空间复杂度是指在计算机中执行算法时所需存储空间的度量，也是数据大小n的函数。

　　公式：S(n) = O( f(n) )，其中f(n)为问题大小为n时占用的内存空间大小。

　　Big O 表示法也适用于空间复杂度。

　　常用算法

　　我们都知道线性表分为无序线性表和有序线性表。

　　无序线性表中的数据没有升序或降序排列，因此在插入和删除时，没有必须遵循的规则。可以在数据末尾插入也可以在数据末尾删除（要删除的数据和最后一个数据交换的位置），但是搜索的时候需要遍历整个数据集，影响效率。

　　一个有序线性表的数据就是这个想法。搜索时，由于数据是有序的，所以可以通过二分法、插值法、斐波那契搜索来实现。但是，插入和删除需要维护一个有序的结构，这会花费很多时间。

　　为了提高插入和删除的效率，引入了二叉排序树。

　　二叉搜索树、平衡二叉搜索树、红黑树、B-树和B+树

　　二叉搜索树的特点：

　　二叉搜索树种最大的特点是左子树的节点必须小于父节点，右子树的节点必须大于父节点。

　　二叉搜索树查找：

　　通过观察上面的二叉搜索树，我们可以知道可以从根节点开始搜索搜索树中的一个值，并与根节点的值进行比较。它小于根节点的值，位于根节点的左侧。在子树中搜索大于根节点的值，在根节点的右子树中搜索。其他节点的行为与根节点的行为相同。

　　从这里开始，你可以得到递归算法：

　　遍历打印可以使用中序遍历，打印结果是一个从小到大的有序数组。

　　二叉搜索树插入：

　　新节点插入到树的叶子中，而不改变树中原创节点的组织结构。插入节点的成本与查找不存在数据的成本完全相同。

　　二元排序的插入是基于二元排序的搜索。原因很简单。将节点添加到合适的位置就是通过搜索找到合适的位置并将节点直接放入其中。

　　先说插入函数。SearchBST中的指针p（BiTree T, int key, BiTree f, BiTree *p）起到了非常重要的作用：

　　二叉搜索树删除：

　　二叉树的删除可以看作是二叉树最复杂的操作。删除时需要考虑的情况有很多：

　　删除的节点是叶节点。删除的节点只有左子节点。删除的节点只有右子节点。有两个子节点。

　　二叉搜索树的效率总结：找到最好的时间复杂度O(logN)，最坏的时间复杂度O(N)。插入和删除操作算法简单，时间复杂度与搜索相似。

　　高度平衡二叉搜索树（Height-Balanced Binary Search Tree）是一种二叉排序树，其中每个节点的左子树和右子树的高度差不超过1（小于等于< @1）。

　　二叉树的平衡因子等于节点左子树的深度减去右子树的深度，称为平衡因子。平衡因子只能是-1、0、1。

　　根距插入节点最近且平衡因子绝对值大于1的子树，称为最小不平衡子树。

　　平衡二叉搜索树是构造二叉树的过程。每当一个节点插入时，判断是否是因为插入树破坏了树的平衡。如果是，找到最小的不平衡树。在保持二叉树特性的前提下，调整最小不平衡子树中节点之间的链接关系，并进行相应的旋转，使其成为新的平衡子树。所以主要还是要注意：逐步调整，逐步平衡。

　　在左手和右手的过程中，我们可以看到平衡因子从(0, 1, 2）到(0, 0, 0）)，这是一个转换的过程从不平衡状态到平衡状态，这也是AVL树逐步调整的核心。

　　让我们观察一个复杂的情况：

<p>插入新节点17，使13(-2）的BF和21(