相邻搜索算法

❶ 运动估计的搜索算法

匹配误差函数，可以用各种优化方法进行最小化，这就需要我们开发出高效的运动搜索算法，
主要的几种算法归纳如下： 为当前帧的一个给定块确定最优位移矢量的全局搜索算法方法是：在一个预先定义的搜索区域
内，把它与参考帧中所有的候选块进行比较，并且寻找具有最小匹配误差的一个。这两个块之间的
位移就是所估计的 MV，这样做带来的结果必然导致极大的计算量。
选择搜索区域一般是关于当前块对称的，左边和右边各有 Rx 个像素，上边和下边各有 Ry个像素。
如果已知在水平和垂直方向运动的动态范围是相同的，那么 Rx=Ry=R。估计的精度是由搜索的步长决定的，步长是相邻两个候选块在水平或者垂直方向上的距离。通常，沿着两个方向使用相同的步长。在最简单的情况下，步长是一个像素，称为整数像素精度搜索，该种算法也称为无损搜索算法。 由于在穷尽块匹配算法中搜索相应块的步长不一定是整数，一般来说，为了实现 1/K像素步长，对参考帧必须进行 K倍内插。根据实验证明，与整像素精度搜索相比，半像素精度搜索在估计精度上有很大提高，特别是对于低清晰度视频。
但是，应用分数像素步长，搜索算法的复杂性大大增加，例如，使用半像素搜索，搜索点的总数比整数像素精度搜索大四倍以上。
那么，如何确定适合运动估计的搜索步长，对于视频编码的帧间编码来说，即使得预测误差最小化。 快速搜索算法和全局搜索算法相比，虽然只能得到次最佳的匹配结果，但在减少运算量方面效果显着。
1） 二维对数搜索法
这种算法的基本思路是采用大菱形搜索模式和小菱形搜索模式，步骤如图 6.4.20 所示，从相应于零位移的位置开始搜索，每一步试验菱形排列的五个搜索点。下一步，把中心移到前一步找到的最佳匹配点并重复菱形搜索。当最佳匹配点是中心点或是在最大搜索区域的边界上时，就减小搜索步长（菱形的半径） 。否则步长保持不变。当步长减小到一个像素时就到达了最后一步，并且在这最
后一步检验九个搜索点。初始搜索步长一般设为最大搜索区域的一半。
其后这类算法在搜索模式上又做了比较多的改进，在搜索模式上采用了矩形模式，还有六边形模式、十字形模式等等。
2） 三步搜索法
这种搜索的步长从等于或者略大于最大搜索范围的一半开始。第一步，在起始点和周围八个 “1”标出的点上计算匹配误差，如果最小匹配误差在起始点出现，则认为没有运动；第二步，以第一步中匹配误差最小的点（图中起始点箭头指向的“1”）为中心，计算以“2”标出的 8个点处的匹配误差。注意，在每一步中搜索步长搜都比上一步长减少一半，以得到更准确的估计；在第三步以后就能得到最终的估计结果，这时从搜索点到中心点的距离为一个像素。
但是，上述一些快速算法更适合用于估计运动幅度比较大的场合，对于部分运动幅度小的场合，它们容易落入局部最小值而导致匹配精度很差，已经有很多各种各样的视频流证明了这一点。
现在，针对这一缺点，国内外诸多专家学者也提出了相应的应对措施，特别是针对H.264编码标准要求的一些快速算法的改进，并取得卓越的效果。例如[7]中提到的基于全局最小值具有自适应性的快速算法，这种算法通过在每一搜索步骤选择多个搜索结果，基于这些搜索结果之间的匹配误差的不同得到的最佳搜索点，因而可以很好地解决落入局部最小值的问题。
[8]中提到一种适用于H．264的基于自适应搜索范围的快速运动估计算法，经过实验证明对于如salesman等中小运动序列，其速度可接近全局搜索算法的400倍，接近三步搜索算法的4倍；而对于大运动序列，如table tennis，该算法则会自动调节搜索点数以适应复杂的运动。当从总体上考察速度方面的性能时，可以看到，该算法平均速度是全局搜索算法的287．4倍，三步搜索的2．8倍。 分级搜索算法的基本思想是从最低分辨率开始逐级精度的进行不断优化的运动搜索策略，首先取得两个原始图象帧的金子塔表示，从上到下分辨率逐级变细，从顶端开始，选择一个尺寸比较大的数据块进行一个比较粗略的运动搜索过程，对在此基础上进行亚抽样（即通过降低数据块尺寸（或提高抽样分辨率）和减少搜索范围的办法）进行到下一个较细的级来细化运动矢量，而一个新的搜索过程可以在上一级搜索到的最优运动矢量周围进行。在亚抽样的过程中也有着不同的抽样方式和抽样滤波器。这种方法的优点是运算量的下降比例比较大，而且搜索的比较全面。
缺点是由于亚抽样或者滤波器的采用而使内存的需求增加，另外如果场景细节过多可能会容易落入局部最小点。 由于物体的运动千变万化，很难用一种简单的模型去描述，也很难用一种单一的算法来搜索最佳运动矢量，因此实际上大多采用多种搜索算法相组合的办法，可以在很大程度上提高预测的有效性和鲁棒性。
事实上，在运动估计时也并不是单一使用上述某一类搜索算法，而是根据各类算法的优点灵活组合采纳。在运动幅度比较大的情况下可以采用自适应的菱形搜索法和六边形搜索法，这样可以大大节省码率而图象质量并未有所下降。在运动图象非常复杂的情况下，采用全局搜索法在比特数相对来说增加不多的情况下使得图象质量得到保证。 H.264 编码标准草案推荐使用 1/4分数像素精度搜索。[6]中提到在整像素搜索时采用非对称十字型多层次六边形格点运动搜索算法，然后采用钻石搜索模型来进行分数像素精度运动估计。
解码器要求传送的比特数最小化，而复杂的模型需要更多的比特数来传输运动矢量，而且易受噪声影响。因此，在提高视频的编码效率的技术中，运动补偿精度的提高和比特数最小化是相互矛盾的，这就需要我们在运动估计的准确性和表示运动所用的比特数之间作出折中的选择。它的效果与选用的运动模型是密切相关的。

❷ 搜索技术

问题求解过程是 搜索答案（目标） 的过程，所以问题求解技术也叫做搜索技术——通过对 状态空间 的搜索而求解问题的技术。

问题可形式化地定义成四个组成部分

在解题过程中 达到过的所有状态 的集合。不同于状态空间，搜索空间是其中一部分。状态空间和搜索空间都属于 过程性知识表示 。

八数码问题详解

两种搜索技术

无信息搜索策略也称 盲目搜索 ：没有任何附加信息，只有生成后继和区分目标和非目标状态。
五种盲目搜索策略有：广度优先搜索，代价一直搜索，深度优先搜索，深度有限搜索，迭代深入深度优先搜索。

从四种度量来评价广度优先搜索

性能：通常使用递归函数实现，一次对当前节点的子节点调用该函数。相比广度优先，内存需求少(分支因子 * 最大深度+1)。但 不是完备的也不是最优的 *。

深度优先搜索的无边界问题可以通过提供一个 预先设定的深度限制I 来解决。深度=I的节点当作无后继节点看待；虽然解决了无边界问题，但 有可能无解 ； 如果选择I>d则深度优先原则也不是最优解 。

每次改变限制深度 ，多次调用深度有限搜索，当 搜索到达最浅的目标节点深度 时就可以发现目标节点，称为迭代深入深度优先搜索。这种搜索结合了广度优先和深度优先两种搜索方式的优势。 解决了深度优先的完备性问题 。空间需求是(b * d),时间需求是(b d )。当搜索空间很大且深度未知时，迭代深入深度优先搜索 是首选的无信息搜索方式 。

迭代深入搜索中因为多次重复搜索上层节点，使部分状态反复生成，看起来很浪费内存空间和时间。但是因为 在分支因子比较均衡的搜索树 中， 多数节点都是叶子节点 *（叶子节点数远大于上层节点总和），所以上层节点多次生成的影响并不大，与广度优先相比，效率还是很高。

用于目标状态已知，求解过程的问题。通常通过 广度优先搜索 实现。从 起始节点和目标状态两个方向 开始扩展，当 两个OPEN表出现交集 时表明搜索到了一条从起始到结果的一条路径。 缺点 ：算法编写难。但一旦实现，效率要远高于其他盲目搜索。

评价函数 ：f ( n ) = h ( n ) ；评价函数等于启发函数
解释：贪婪最佳优先搜索中 无条件选择 当前离目标最近（代价最小）的结点进行扩展。但是 局部最佳不是全局最佳，即非最优。 其中h（ n ）称为 启发函数 ，是从节点n到目标节点的最低代价的 估计值 。

评价函数 ：f ( n ) = g ( n ) + h ( n )；评价函数等于启发函数加路径耗散函数
解释：

另，对于有向图的搜索还可以采用图搜索方式。详情： 图搜索和树搜索详解

称启发函数是可采纳的，如果h( n ) 满足 h( n ) ≤ h * ( n ) ，其中 h * ( n )是从当前节点 n到达目标的最低真实代价 ，即h( n )的估值永远小于真实耗散值；因为f ( n ) = g ( n ) + h ( n )，且g（n）为已知常数，所以 f（n）永远不会高估经过结点n的解的实际代价 ，所以是最优解。

如果采用 A* 图搜索算法，则不一定返回最优解 。因为如果最优路径不是第一个生成的，可能因为有重复状态而被丢弃了。见上个链接： 图搜索和树搜索详解

如果对于每个结点n，以及n的行为a产生的后继结点n'满足如下公式： h ( n ) ≤ c ( n, n', a) + h( n ') （c ( n, n', a)可以理解为g（n'）），则称这个h ( n )启发函数是一致的。

A* 搜索由初始结点出发开始搜索，以同心带状增长f（n）耗散值的方式扩展结点。如果h（n）= 0 意味着只按g（n）值排序，即同心带为“圆形”。使用启发函数则同心带向目标节点拉伸（椭圆越来越扁）。

如果C*是最优路径的耗散值，则：

A* 搜索的关键就是 设计可采纳的或一致的（单调的）启发函数 。

绝不高估 到达目标的耗散值，尽可能的接近真实耗散值

子问题的解耗散是完整问题的 耗散下界 。

从实例中学习，每个实例包含了解路径上各状态及其到达解的耗散值。每个最优解实例提供了可学习h(n)的实例，由此产生可预测其他状态解消耗的启发函数。

联机搜索智能体需要行动和感知，然后扩展当前状态的环境地图

智能体初始位置在S，其已知信息为：

A* 搜索在不同子空间结点的跳跃式扩展， 模拟而非实际行动 ；联机搜索只扩展实际占据的结点——采用深度优先。 联机搜索必须维护一个回溯表

博弈搜索是智能体之间的对抗，每个智能体的目的是冲突的。本节需要解决两个问题：如何搜索到取胜的 路径 /如何提高搜索 效率 。相应的办法是 极大极小决策和α-β剪枝 。

两个智能体博弈时，可令一方为MAX，一方为MIN。MAX希望终局得分高，MIN希望终局得分低。

博弈搜索中，最优解是导致取胜的终止状态的一系列招数。MAX制定取胜策略时，必须不断考虑MIN应对条件下如何取胜。

如果博弈双方 都按照最优策略 进行，则一个结点的 极大极小值就是对应状态的效用值

简单的递归算法——按照定义计算每个后继结点的极大极小值/搜索是从目标到初始结点的 反向推导

如果博弈树最大深度为m，每个节点的合法招数为b，则

剪掉那些不可能影响最后决策的分支，返回和极大极小值相同的结果。
α-β剪枝可以应用树的任何深度。

如果在结点n的父节点或更上层有一个更好的选择m，则在搜索中永远不会到达n。

很大程度上取决于检查后继节点的次序—— 应先检查那些可能更好的后继 。如果能先检查那些最好的后继，则 时间复杂度为O(b (d/2) ) 。优于极大极小算法的O(b d )

许多问题中 路径是无关紧要的 。从当前状态出发，通常 只移动到相邻状态 ，且路径不保留。

内存消耗少，通常是一个常数。

向目标函数值增加的方向持续移动，直到相邻状态没有比它更高的值。 取到一个局部最优则终止 。
使新状态估计值优于当前状态值和其他所有候补结点值，则取新状态放弃其他状态。

将 爬山法 （停留在局部最优）和 随机行走 （下山）以某种方式结合，同时拥有 完备性和效率 。
技巧是，概率足够大可以弹出局部最优；但概率不能太大而弹出全局最优。

按照模拟退火的思想， T随时间逐渐减小 。如果 T下降的足够慢 ，则找到全局最优解是 完备的 。

随机移动，如果评价值改善则采纳； 否则以小于一的概率接受 。

从 k个随机生成的状态开始 ，每步生成k个结点的所有后继状态。如果其中之一是目标状态则停止算法；否则从全部后继状态中选择最佳的k个状态继续搜索。
有用的信息 在k个并行的 搜索线程之间传递 ，算法会很快放弃没有成果的搜索，而把资源放在取得最大进展的搜索上。

局部剪枝搜索的变种。因为局部剪枝搜索搜索是贪婪的，因而用随机剪枝搜索代替。不是选择最好的k个后代，而是按照一定概率选取k个后继状态。

类似于自然界的选择过程。状态对应个体，其 值对应适应性 ，后代就是状态。因此如果k个状态缺乏多样性，则局部搜索会受影响。

局部剪枝算法已有 群体进化 （优胜劣汰）的趋势。遗传算法是随机剪枝的变种。

包括选择，交叉和变异

又称繁殖，按照一定的概率选择两对个体生成后继状态

计算每个个体i被选中的概率： pi = f(i) / [f(1)+...+f(n)] .然后根据概率将圆盘分为n个扇形，每个扇形大小为 2Πpi 。

繁殖过程中，后代是父串在杂交点上进行杂交得来的。这样一来，后代子串保留了父串的优良特性又与父串不同。

首先以概率p随机在种群中选择pa和pb两个个体，再从{1,2,...,m}中（可以按一定概率，如两边概率小于中间概率）选择一个数i，作为交叉点。而后将两个个体的交叉点后面的部分交换。

在新生成的后继状态中各个位置都会按照一个 独立的很小的概率 随机变异。
变异时要做到 一致变异 ；即相同概率地变异所有个体的每一位。

结合了“上山”和随机行走，并在并行搜索线程之间交换信息。遗传算法的 最大优点在于杂交 。因为杂交可以 将独立发展的若干个砖块组合起来 ，提高搜索的粒度。

个体编码某些位置上数字仍未确定的一个状态子串。

如果 一个模式的实例的平均适应值超过均值 ，则种群内这个模式的实例数量会随时间而增长（优胜）；反之则减少（劣汰）

长度较短，高于平均适应度的模式在遗传算子的作用下， 相互结合 ，能生成长度较长、适应度较高的 模式 。

Constraint Satisfying Problem，CSP。

由一个 变量集合{X1~Xn} 和一个 约束集合{C1~Cn} ；每个变量都有一个 非空可能的值域Di 。每个约束指定了 若干变量的一个子集内各变量的赋值范围 。

CSP的一个状态是，对一些或每个变量赋值

一组既是 相容赋值 又是 完全赋值 的对变量的赋值就是CSP的解。

提前考虑某些约束，以减少搜索空间

若X被赋值，检查与X相连的Y，判断是否满足约束，去掉Y中不满足约束的赋值。（进行某种检验，可以不为有问题的Y集合赋值 ）

❸ 搜索算法的应用案例

(1)题目：黑白棋游戏
黑白棋游戏的棋盘由4×4方格阵列构成。棋盘的每一方格中放有1枚棋子，共有8枚白棋子和8枚黑棋子。这16枚棋子的每一种放置方案都构成一个游戏状态。在棋盘上拥有1条公共边的2个方格称为相邻方格。一个方格最多可有4个相邻方格。在玩黑白棋游戏时，每一步可将任何2个相邻方格中棋子互换位置。对于给定的初始游戏状态和目标游戏状态，编程计算从初始游戏状态变化到目标游戏状态的最短着棋序列。
(2)分析
这题我们可以想到用深度优先搜索来做，但是如果下一步出现了以前的状态怎么办？直接判断时间复杂度的可能会有点大，这题的最优解法是用广度优先搜索来做。我们就可以有初始状态按照广度优先搜索遍历来扩展每一个点，这样到达目标状态的步数一定是最优的（步数的增加时单调的）。但问题是如果出现了重复的情况我们就必须要判重，但是朴素的判重是可以达到状态数级别的，其实我们可以考虑用hash表来判重。
Hash表：思路是根据关键码值进行直接访问。也就是说把一个关键码值映射到表中的一个位置来访问记录的过程。在Hash表中，一般插入，查找的时间复杂度可以在O（1）的时间复杂度内搞定。对于这一题我们可以用二进制值表示其hash值，最多2^16次方，所以我们开个2^16次方的表记录这个状态出现没有，这样可以在O（1）的时间复杂度内解决判重问题。
进一步考虑：从初始状态到目标状态，必定会产生很多无用的状态，那还有什么优化可以减少这时间复杂度？我们可以考虑把初始状态和目标状态一起扩展，这样如果初始状态的某个被扩展的点与目标状态所扩展的点相同时，那这两个点不用扩展下去，而两个扩展的步数和也就是答案。
上面的想法是双向广度优先搜索：
就像图二一样，多扩展了很多不必要的状态。
从上面一题可以看到我们用到了两种优化方法，即Hash表优化和双向广搜优化。一般的广度优先搜索用这两个优化就足以解决。

❹ 常见查找和排序算法

查找成功最多要n 次，平均（n+1）/2次， 时间复杂度为O(n) 。
优点：既适用顺序表也适用单链表，同时对表中元素顺序无要求，给插入带来方便，只需插入表尾即可。
缺点：速度较慢。

改进：在表尾设置一个岗哨，这样不用去循环判断数组下标是否越界，因为最后必然成立。

适用条件：

二分查找的判定树不仅是二叉排序树，而且是一棵理想平衡树。 时间复杂度为O(lbn) 。

循环实现

递归实现

待排序的元素需要实现 Java 的 Comparable 接口，该接口有 compareTo() 方法，可以用它来判断两个元素的大小关系。

从数组中选择最小元素，将它与数组的第一个元素交换位置。再从数组剩下的元素中选择出最小的元素，将它与数组的第二个元素交换位置。不断进行这样的操作，直到将整个数组排序。

选择排序需要 ~N2/2 次比较和 ~N 次交换，==它的运行时间与输入无关==，这个特点使得它对一个已经排序的数组也需要这么多的比较和交换操作。

从左到右不断 交换相邻逆序的元素 ，在一轮的循环之后，可以让未排序的最大元素上浮到右侧。

在一轮循环中，如果没有发生交换，那么说明数组已经是有序的，此时可以直接退出。

每次都 将当前元素插入到左侧已经排序的数组中 ，使得插入之后左侧数组依然有序。

对于数组 {3, 5, 2, 4, 1}，它具有以下逆序：(3, 2), (3, 1), (5, 2), (5, 4), (5, 1), (2, 1), (4, 1)，插入排序每次只能交换相邻元素，令逆序数量减少 1，因此插入排序需要交换的次数为逆序数量。

==插入排序的时间复杂度取决于数组的初始顺序，如果数组已经部分有序了，那么逆序较少，需要的交换次数也就较少，时间复杂度较低==。

对于大规模的数组，插入排序很慢，因为它只能交换相邻的元素，每次只能将逆序数量减少 1。希尔排序的出现就是为了解决插入排序的这种局限性，它通过交换不相邻的元素，每次可以将逆序数量减少大于 1。

希尔排序使用插入排序对间隔 h 的序列进行排序。通过不断减小 h，最后令 h=1，就可以使得整个数组是有序的。

希尔排序的运行时间达不到平方级别，使用递增序列 1, 4, 13, 40, ... 的希尔排序所需要的比较次数不会超过 N 的若干倍乘于递增序列的长度。后面介绍的高级排序算法只会比希尔排序快两倍左右。

归并排序的思想是将数组分成两部分，分别进行排序，然后归并起来。

归并方法将数组中两个已经排序的部分归并成一个。

将一个大数组分成两个小数组去求解。

因为每次都将问题对半分成两个子问题，这种对半分的算法复杂度一般为 O(NlogN)。

先归并那些微型数组，然后成对归并得到的微型数组。

取 a[l] 作为切分元素，然后从数组的左端向右扫描直到找到第一个大于等于它的元素，再从数组的右端向左扫描找到第一个小于它的元素，交换这两个元素。不断进行这个过程，就可以保证左指针 i 的左侧元素都不大于切分元素，右指针 j 的右侧元素都不小于切分元素。当两个指针相遇时，将切分元素 a[l] 和 a[j] 交换位置。

快速排序是原地排序，不需要辅助数组，但是递归调用需要辅助栈。

快速排序最好的情况下是每次都正好将数组对半分，这样递归调用次数才是最少的。这种情况下比较次数为 CN=2CN/2+N，复杂度为 O(NlogN)。

最坏的情况下，第一次从最小的元素切分，第二次从第二小的元素切分，如此这般。因此最坏的情况下需要比较 N2/2。为了防止数组最开始就是有序的，在进行快速排序时需要随机打乱数组。

因为快速排序在小数组中也会递归调用自己，对于小数组，插入排序比快速排序的性能更好，因此在小数组中可以切换到插入排序。

最好的情况下是每次都能取数组的中位数作为切分元素，但是计算中位数的代价很高。一种折中方法是取 3 个元素，并将大小居中的元素作为切分元素。

对于有大量重复元素的数组，可以将数组切分为三部分，分别对应小于、等于和大于切分元素。

三向切分快速排序对于有大量重复元素的随机数组可以在线性时间内完成排序。

快速排序的 partition() 方法，会返回一个整数 j 使得 a[l..j-1] 小于等于 a[j]，且 a[j+1..h] 大于等于 a[j]，此时 a[j] 就是数组的第 j 大元素。

可以利用这个特性找出数组的第 k 大的元素。

该算法是线性级别的，假设每次能将数组二分，那么比较的总次数为 (N+N/2+N/4+..)，直到找到第 k 个元素，这个和显然小于 2N。

堆中某个节点的值总是大于等于其子节点的值，并且堆是一颗完全二叉树。

堆可以用数组来表示，这是因为堆是完全二叉树，而完全二叉树很容易就存储在数组中。位置 k 的节点的父节点位置为 k/2，而它的两个子节点的位置分别为 2k 和 2k+1。这里不使用数组索引为 0 的位置，是为了更清晰地描述节点的位置关系。

在堆中，当一个节点比父节点大，那么需要交换这个两个节点。交换后还可能比它新的父节点大，因此需要不断地进行比较和交换操作，把这种操作称为上浮。

类似地，当一个节点比子节点来得小，也需要不断地向下进行比较和交换操作，把这种操作称为下沉。一个节点如果有两个子节点，应当与两个子节点中最大那个节点进行交换。

将新元素放到数组末尾，然后上浮到合适的位置。

从数组顶端删除最大的元素，并将数组的最后一个元素放到顶端，并让这个元素下沉到合适的位置。

把最大元素和当前堆中数组的最后一个元素交换位置，并且不删除它，那么就可以得到一个从尾到头的递减序列，从正向来看就是一个递增序列，这就是堆排序。

一个堆的高度为logN，因此在堆中插入元素和删除最大元素的复杂度都为 logN。

对于堆排序，由于要对 N 个节点进行下沉操作，因此复杂度为 NlogN。

堆排序是一种原地排序，没有利用额外的空间。

现代操作系统很少使用堆排序，因为它无法利用局部性原理进行缓存，也就是数组元素很少和相邻的元素进行比较和交换。

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，==计数排序要求输入的数据必须是有确定范围的整数==。

当输入的元素是 n 个 0 到 k 之间的整数时，它的==运行时间是 O(n + k)==。计数排序不是比较排序，排序的速度快于任何比较排序算法。由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。比较适合用来排序==小范围非负整数数组的数组==。

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

当输入数据均匀分配到每一个桶时最快，当都分配到同一个桶时最慢。

实间复杂度N*K

快速排序是最快的通用排序算法，它的内循环的指令很少，而且它还能利用缓存，因为它总是顺序地访问数据。它的运行时间近似为 ~cNlogN，这里的 c 比其它线性对数级别的排序算法都要小。

使用三向切分快速排序，实际应用中可能出现的某些分布的输入能够达到线性级别，而其它排序算法仍然需要线性对数时间。

❺ 怎样才能快速搜索路由表有哪些着名的搜索算法

有三个路由器，a，b和c。路由器a的两个网络接口f0和s0
分别连接在
10.1.0.0和10.2.0.0网段上；路由器b的两个网络接口s0和s1
分别连接在
10.2.0.0和10.3.0.0网段上；路由器c的两个网络接口s0和e0
分别连接在
10.3.0.0和10.4.0.0网段上；
如上图中各路由表的前两行所示，通过路由表的网络接口到与之直接相连的网
络的网络连接，其向量距离设置为0。这即是最初的路由表。
当路由器b和a以及b和c之间相互交换路由信息后，它们会更新各自的路由表。
例如，路由器b通过网络端口s1收到路由器c的路由信息（10.3.0.0,s0,0）和(10.4.0.0,e0,0)后，在自己的路由表中增加一条(10.4.0.0,s1,1)路由信息。该信息表示：通过路由器b的网络接
口s1可以访问到10.4.0.0网段，其向量距离为1,该向量距离是在路由器c的基础上加1获得的。
同样道理，路由器b还会产生一条(10.1.0.0,s0,1)路由，这条路由是通过网络端口s0从路由器a
获得的。如此反复，直到最终收敛，形成图中所示的路由表。
概括地说，距离向量算法要求每一个路由器把它的整个路由表发送给与它直接连接的其它路由
器。路由表中的每一条记录都包括目标逻辑地址、相应的网络接口和该条路由的向量距离。当一个路
由器从它的相邻处收到更新信息时，它会将更新信息与本身的路由表相比较。如果该路由器比较出一条
新路由或是找到一条比当前路由更好的路由时，它会对路由表进行更新：将从该路由器到邻居之间的
向量距离与更新信息中的向量距离相加作为新路由的向量距离。

❻ 在用邻接表表示图时,对图进行深度优先搜索遍历的算法的时间复杂度为()

因为当相邻矩阵的大部分被破坏时，矩阵中的所有元素都需要扫并追踪到，且元素个数为n＾2，自然算法为O（n＾2）。

所以邻接表只存储边或弧，如果扫描邻接表，当然会得到O（n＋e）其中n是顶点的数量，e的边或弧的数量。

设有n个点，e条边

邻接矩阵：矩阵包含n＾2个元素，在算法中共n个顶点，对每个顶点都要遍历n次，所以时间复杂度为O（n＾2）。

邻接表：包含n个头结点和e个表结点，算法中对所有结点都要遍历一次，所以时间复杂度为O（n+e）顺便，对于广度优先算法的时间复杂度，也是这样。

(6)相邻搜索算法扩展阅读：

邻接表是图的最重要的存储结构之一，描述了图上的每个点。创建一个容器对于每一个图的顶点（n顶点n容器）和节点在第i个容器包含所有相邻顶点的顶点Vi。事实上，我们经常使用的邻接矩阵是一个邻接表的边集不离散化每一个点。

在有向图中，描述每个点与另一个节点连接的边(在a点->点B)。

在无向图中，描述每个点上的所有边（A点和B点的情况）

邻接表对应的图存储方法称为边集表。此方法将所有边存储在容器中。