算法退化性
① 什么情况下，KMP算法的性能会退化为朴素匹配算法
（1）未改进的模式匹配算法的时间复杂度为O（nm），但在一般情况下，其实际的执行时间接近O（n＋m），因此至今仍被采用。
（2）KMP算法仅当模式与主串之间存在许多“部分”匹配的情况下才显得比未改进的模式匹配快。
（2）KMP算法的最大特点是指示主串的指针不需要回溯，在整个匹配过程中，对主串仅需要从头至尾扫描一遍，这对处理存储在外存上的大文件是非常有效的。
(1)算法退化性扩展阅读：
KMP算法是三位学者在 Brute-Force算法的基础上同时提出的模式匹配的改进算法。Brute- Force算法在模式串中有多个字符和主串中的若干个连续字符比较都相等,但最后一个字符比较不相等时，主串的比较位置需要回退。KMP算法在上述情况下，主串位置不需要回退,从而可以大大提高效率。
如果模式P与目标T(或其子串)存在某种程度的相似,则认为匹配成功。常用的衡量字符串相似度的方法是根据一个串转换成另一个串所需的基本操作数目来确定。基本操作由字符串的插入、删除和替换来组成。
② 遗传算法 图像恢复 退化过程怎么确定
就是要尽可能恢复退化图像的本来面目，它是沿图像退化的逆过程进行处理。
典型的图像复原是根据图像退化的先验知识建立一个退化模型，以此模型为基础，采用各种逆退化处理方法进行恢复，使图像质量得到改善。
图像复原和图像增强的区别：图像增强不考虑图像是如何退化的，而是试图采用各种技术来增强图像的视觉效果。因此，图像增强可以不顾增强后的图像是否失真，只要看得舒服就行。而图像复原就完全不同，需知道图像退化的机制和过程等先验知识，据此找出一种相应的逆处理方法，从而得到复原的图像。如果图像已退化，应先作复原处理，再作增强处理。二者的目的都是为了改善图像的质量。
资料： 图像恢复的目的是设法改进图像的质量，以提高视觉观察或进一步数字处理的效果。从这个意义上看，图像恢复与图像增强的目的相同。差别是图像恢复后的图像可看成是原始图像逆退化过程的结果。因此，图像恢复有时候称作客观图像增强。恢复技术可以是整体的也可以是局部的，它们可以在某个频域或空间域中实现。例如消除一个具有已知频率的干扰模式，最好在频域中进行，其步骤为：傅立叶变换，滤波，傅立叶逆变换。去除几何变形一般是在空间域内完成。
③ 算法是什么
算法是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令。
算法代表着用系统的方法描述解决问题的策略机制，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输察并腊出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间，空间或效率来完成同样的任务。
算法中的指令描述的是一个计算。当其运行时能从一个初始状态和初始输入开始，经过一系列有限而清晰定义的状态，最终产生输出并停止于一个终态，一个状态到另一个状态的转移不一定是确定的。
算法思想：
1、递推法
递推是序列计算机中的一种常用算法，它是按照一定的规律来计算序列中的每个项，通常是通过计算机前面的一些项来得出序列中的指定项的值。其思想是把一个复杂蔽卜的庞大的计算过程转化为简单过程的多次重复，该算法利用了计算机速度快和不知疲倦的机器特点。
2、递归法
程序调用自身的编程技巧称为递归，一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法。它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需败滑要的多次重复计算。
以上内容参考：网络—算法
④ 比较算法优缺点：
作业调度算法 .
1.先来先服务（FCFS, First Come First Serve）是最简单的调度算法，按先后顺序进行调度。
定义：
按照作业提交或进程变为就绪状态的先后次序，分派CPU；
当前作业或进程占用CPU，直到执行完或阻塞，才出让CPU（非抢占方式）。
在作业或进程唤醒后（如I/O完成），并不立即恢复执行，通常等到当前作业或进程出让CPU。
适用场景：
比较有利于长作业，而不利于短作业。因为长作业会长时间占据处理机。
有利于CPU繁忙的作业，而不利于I/O繁忙的作业。
算法实现原理图：
2. 轮转法(Round Robin)
轮转法是让每个进程在就绪队列中的等待时间与享受服务的时间成正比例。
定义：
将系统中所有的就绪进程按照FCFS原则，排成一个队列。
每次调度时将CPU分派给队首进程，让其执行一个时间片。时间片的长度从几个ms到几百ms。
在一个时间片结束时，发生时钟中断。
调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程。
进程可以未使用完一个时间片，就出让CPU（如阻塞）。
时间片长度的确定：
时间片长度变化的影响
过长－>退化为FCFS算法，进程在一个时间片内都执行完，响应时间长。
过短－>用户的一次请求需要多个时间片才能处理完，上下文切换次数增加，响应时间长。
对响应时间的要求：T(响应时间)=N(进程数目)*q(时间片)
就绪进程的数目：数目越多，时间片越小
系统的处理能力：应当使用户输入通常在一个时间片内能处理完，否则使响应时间，平均周转时间和平均带权周转时间延长。
算法实现原理图：
3. 多级反馈队列算法(Round Robin with Multiple Feedback)
多级反馈队列算法是轮转算法和优先级算法的综合和发展。
定义：
设置多个就绪队列，分别赋予不同的优先级，如逐级降低，队列1的优先级最高。每个队列执行时间片的长度也不同，规定优先级越低则时间片越长，如逐级加倍。
新进程进入内存后，先投入队列1的末尾，按FCFS算法调度；若按队列1一个时间片未能执行完，则降低投入到队列2的末尾，同样按FCFS算法调度；如此下去，降低到最后的队列，则按“时间片轮转”算法调度直到完成。
仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执行。如果进程执行时有新进程进入较高优先级的队列，则抢先执行新进程，并把被抢先的进程投入原队列的末尾。
优点：
为提高系统吞吐量和缩短平均周转时间而照顾短进程。
为获得较好的I/O设备利用率和缩短响应时间而照顾I/O型进程。
不必估计进程的执行时间，动态调节
几点说明：
I/O型进程：让其进入最高优先级队列，以及时响应I/O交互。通常执行一个小时间片，要求可处理完一次I/O请求的数据，然后转入到阻塞队列。
计算型进程：每次都执行完时间片，进入更低级队列。最终采用最大时间片来执行，减少调度次数。
I/O次数不多，而主要是CPU处理的进程。在I/O完成后，放回优先I/O请求时离开的队列，以免每次都回到最高优先级队列后再逐次下降。
为适应一个进程在不同时间段的运行特点，I/O完成时，提高优先级；时间片用完时，降低优先级。
算法实现原理图：
4. 优先级法（Priority Scheling）
优先级算法是多级队列算法的改进，平衡各进程对响应时间的要求。适用于作业调度和进程调度，可分成抢先式和非抢先式。
静态优先级：
作业调度中的静态优先级大多按以下原则确定：
由用户自己根据作业的紧急程度输入一个适当的优先级。
由系统或操作员根据作业类型指定优先级。
系统根据作业要求资源情况确定优先级。
进程的静态优先级的确定原则：
按进程的类型给予不同的优先级。
将作业的情态优先级作为它所属进程的优先级。
动态优先级：
进程的动态优先级一般根据以下原则确定：
根据进程占用有CPU时间的长短来决定。
根据就绪进程等待CPU的时间长短来决定。
5．短作业优先法（SJF, Shortest Job First）
短作业优先又称为“短进程优先”SPN(Shortest Process Next)；这是对FCFS算法的改进，其目标是减少平均周转时间。
定义：
对预计执行时间短的作业（进程）优先分派处理机。通常后来的短作业不抢先正在执行的作业。
SJF的特点：
(1) 优点：
比FCFS改善平均周转时间和平均带权周转时间，缩短作业的等待时间；
提高系统的吞吐量；
(2) 缺点：
对长作业非常不利，可能长时间得不到执行；
未能依据作业的紧迫程度来划分执行的优先级；
难以准确估计作业（进程）的执行时间，从而影响调度性能。
SJF的变型：
“最短剩余时间优先”SRT(Shortest Remaining Time)（允许比当前进程剩余时间更短的进程来抢占）
“最高响应比优先”HRRN(Highest Response Ratio Next)（响应比R = (等待时间 + 要求执行时间) / 要求执行时间，是FCFS和SJF的折衷）
6. 最高响应比优先法(HRN，Highest Response_ratio Next)
最高响应比优先法是对FCFS方式和SJF方式的一种综合平衡。FCFS方式只考虑每个作业的等待时间而未考虑执行时间的长短，而SJF方式只考虑执行时间而未考虑等待时间的长短。因此，这两种调度算法在某些极端情况下会带来某些不便。HRN调度策略同时考虑每个作业的等待时间长短和估计需要的执行时间长短，从中选出响应比最高的作业投入执行。
响应比R定义如下： R =(W+T)/T = 1+W/T
其中T为该作业估计需要的执行时间，W为作业在后备状态队列中的等待时间。每当要进行作业调度时，系统计算每个作业的响应比，选择其中R最大者投入执行。这样，即使是长作业，随着它等待时间的增加，W / T也就随着增加，也就有机会获得调度执行。这种算法是介于FCFS和SJF之间的一种折中算法。由于长作业也有机会投入运行，在同一时间内处理的作业数显然要少于SJF法，从而采用HRN方式时其吞吐量将小于采用SJF 法时的吞吐量。另外，由于每次调度前要计算响应比，系统开销也要相应增加。