不同算法优劣

⑴ 简述各种排序算法的优缺点

一、冒泡排序
已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。首先比较a[1]与 a[2]的值，若a[1]大于a[2]则交换 两者的值，否则不变。再比较a[2]与a[3]的值，若a[2]大于a[3]则交换两者的值，否则不变。再比 较a[3]与a[4]，以此 类推，最后比较a[n-1]与a[n]的值。这样处理一轮后，a[n]的值一定是这组数据中最大的。再对a[1]~a[n- 1]以相同方法 处理一轮，则a[n-1]的值一定是a[1]~a[n-1]中最大的。再对a[1]~a[n-2]以相同方法处理一轮，以此类推。共处理 n-1 轮 后a[1]、a[2]、……a[n]就以升序排列了。
优点：稳定；
缺点：慢，每次只能移动相邻两个数据。

二、选择排序
每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数 据元素排完。
选择排序是不稳定的排序方法。
n 个记录的文件的直接选择排序可经过n-1 趟直接选择排序得到有序结果：
①初始状态：无序区为R[1..n]，有序区为空。
②第1 趟排序 在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1 个记录R[1]交换，使R[1..1]和R[2..n]分别变 为记录个数增加1 个的新有序区和记录个数减少1 个的新无序区。
③第i 趟排序
第i 趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R(1≤i≤n-1)。该趟 排序从当前无序区中选出关键字最 小的记录 R[k]，将它与无序区的第1 个记录R 交换，使R[1..i]和R 分别变为记录个数增加1 个的新有序区和记录个数减少 1 个的新无序区。
这样，n 个记录的文件的直接选择排序可经过n-1 趟直接选择排序得到有序结果。
优点：移动数据的次数已知（n-1 次）；
缺点：比较次数多。

三、插入排序
已知一组升序排列数据a[1]、a[2]、……a[n]，一组无序数据b[1]、 b[2]、……b[m]，需将二者合并成一个升序数列。 首先比较b[1]与a[1]的值，若b[1]大于a[1]，则跳过，比较b[1]与a[2]的值， 若b[1]仍然大于a[2]，则继续跳过，直 到b[1]小于a 数组中某一数据a[x]，则将a[x]~a[n]分别向后移动一位，将b[1]插入到原来 a[x]的位置这就完成了b[1] 的插入。b[2]~b[m]用相同方法插入。（若无数组a，可将b[1]当作n=1 的数组a）
优点：稳定，快；
缺点：比较次数不一定，比较次数越少，插入点后的数据移动越多，特别是当数据总量庞大的时候，但用链表可以解决 这个问题。

四、缩小增量排序
由希尔在1959 年提出，又称希尔排序(shell 排序)。
已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。发现当n 不大时，插入 排序的效果很好。首先取一增 量d(d<n)，将a[1]、a[1+d]、a[1+2d]……列为第一组，a[2]、a[2+d]、 a[2+2d]……列为第二组……，a[d]、a[2d]、a[3d]……="" 列为最后一组以次类推，在各组内用插入排序，然后取d'<d，重复上述操="" 作，直到d="1。"
优点：快，数据移动少；=""
缺点：不稳定，d="" 的取值是多少，应取多少个不同的值，都无法确切知道，只能凭经验来取。=""

五、快速排序=""
快速排序是冒泡排序的改进版，是目前已知的最快的排序方法。
="" 已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。首先任取数据a[x]="" 作为基准。比较a[x]与其它数据并="" 排序，使a[x]排在数据的第k="" 位，并且使a[1]~a[k-1]中的每一个数="" 据a[x]，然后采 用分治的策略分别对a[1]~a[k-1]和a[k+1]~a[n] 两组数据进行快速排序。
优点：极快，数据移动少；
缺点：不稳定。

⑵ 比较算法优缺点：

1.先来先服务先来先服务（FCFS, First Come First Serve）是最简单的调度算法，按先后顺序进行调度。1. 定义按照作业提交或进程变为就绪状态的先后次序，分派CPU；当前作业或进程占用CPU，直到执行完或阻塞，才出让CPU（非抢占方式）。在作业或进程唤醒后（如I/O完成），并不立即恢复执行，通常等到当前作业或进程出让CPU。2.适用场景比较有利于长作业，而不利于短作业。有利于CPU繁忙的作业，而不利于I/O繁忙的作业。
2. 轮转法轮转法(Round Robin)是让每个进程在就绪队列中的等待时间与享受服务的时间成正比例。1. 定义将系统中所有的就绪进程按照FCFS原则，排成一个队列。每次调度时将CPU分派给队首进程，让其执行一个时间片。时间片的长度从几个ms到几百ms。在一个时间片结束时，发生时钟中断。调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程。进程可以未使用完一个时间片，就出让CPU（如阻塞）。2. 时间片长度的确定时间片长度变化的影响过长－>退化为FCFS算法，进程在一个时间片内都执行完，响应时间长。过短－>用户的一次请求需要多个时间片才能处理完，上下文切换次数增加，响应时间长。对响应时间的要求：T(响应时间)=N(进程数目)*q(时间片)就绪进程的数目：数目越多，时间片越小系统的处理能力：应当使用户输入通常在一个时间片内能处理完，否则使响应时间，平均周转时间和平均带权周转时间延长。
3. 多级反馈队列算法多级反馈队列算法(Round Robin with Multiple Feedback)是轮转算法和优先级算法的综合和发展。1. 定义设置多个就绪队列，分别赋予不同的优先级，如逐级降低，队列1的优先级最高。每个队列执行时间片的长度也不同，规定优先级越低则时间片越长，如逐级加倍。新进程进入内存后，先投入队列1的末尾，按FCFS算法调度；若按队列1一个时间片未能执行完，则降低投入到队列2的末尾，同样按FCFS算法调度；如此下去，降低到最后的队列，则按“时间片轮转”算法调度直到完成。仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执行。如果进程执行时有新进程进入较高优先级的队列，则抢先执行新进程，并把被抢先的进程投入原队列的末尾。2.优点为提高系统吞吐量和缩短平均周转时间而照顾短进程。为获得较好的I/O设备利用率和缩短响应时间而照顾I/O型进程。不必估计进程的执行时间，动态调节3. 几点说明I/O型进程：让其进入最高优先级队列，以及时响应I/O交互。通常执行一个小时间片，要求可处理完一次I/O请求的数据，然后转入到阻塞队列。计算型进程：每次都执行完时间片，进入更低级队列。最终采用最大时间片来执行，减少调度次数。I/O次数不多，而主要是CPU处理的进程。在I/O完成后，放回优先I/O请求时离开的队列，以免每次都回到最高优先级队列后再逐次下降。为适应一个进程在不同时间段的运行特点，I/O完成时，提高优先级；时间片用完时，降低优先级。
4. 优先级法优先级算法（Priority Scheling）是多级队列算法的改进，平衡各进程对响应时间的要求。适用于作业调度和进程调度，可分成抢先式和非抢先式。1. 静态优先级作业调度中的静态优先级大多按以下原则确定：由用户自己根据作业的紧急程度输入一个适当的优先级。由系统或操作员根据作业类型指定优先级。系统根据作业要求资源情况确定优先级。进程的静态优先级的确定原则：按进程的类型给予不同的优先级。将作业的情态优先级作为它所属进程的优先级。2. 动态优先级进程的动态优先级一般根据以下原则确定：根据进程占用有CPU时间的长短来决定。根据就绪进程等待CPU的时间长短来决定。
5．短作业优先法短作业优先（SJF, Shortest Job First）又称为“短进程优先”SPN(Shortest Process Next)；这是对FCFS算法的改进，其目标是减少平均周转时间。1. 定义对预计执行时间短的作业（进程）优先分派处理机。通常后来的短作业不抢先正在执行的作业。2. SJF的特点(1) 优点：比FCFS改善平均周转时间和平均带权周转时间，缩短作业的等待时间；提高系统的吞吐量；(2) 缺点：对长作业非常不利，可能长时间得不到执行；未能依据作业的紧迫程度来划分执行的优先级；难以准确估计作业（进程）的执行时间，从而影响调度性能。3. 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 法时的吞吐量。另外，由于每次调度前要计算响应比，系统开销也要相应增加。

⑶ 如何判断算法优劣

算法的好坏是看它的运行效率比如递归一般来说是比较耗时间的，也就是说效率低当然也看具体情况，有的算法在基数小的情况是差不多，性能反而还好点

⑷ 如何衡量一个算法的优劣有哪些标准

如何衡量一个算法的优劣，见人见智。一个好的算法首先是要能够满足场景的需求，其次是在能够最大限度的节省资源（最低成本原则），最后是实现逻辑简单，比较容易理解(本质上也是最低成本原则)。但是，在现实中硬件资源不变，算法不变情况下，算法执行的效率提高，相对应往往是资源消耗增加。一个合格的算法是在一个可以接受的范围内满足场景需求，而一个优秀的算法则是在满足场景需求的基础上，最大限度的节省资源，简化逻辑。

比如我要完成一项计算任务，要求是在5分钟执行完成。现在有算法1:需要执行1分钟，消耗内存8G；算法2需要执行3分钟，需要消耗内存256M。那么，我们应该如何选择呢？首先，这两种方案都能满足我们的需求；其次：算法1的需要消耗的资源是算法2的32倍，算法1的效率是算法2的3倍。在这种满足需求的情况下，往往更倾向于选择算法2。衡量一个算法的优劣往往要评估多方因素，结合实践，综合比较最终得出结论。

衡量一个算法的的标准主要有3个： 算法的执行效率 ， 算法的内存消耗 和 算法的稳定性 。

⑸ 深度优先算法 和 宽度优先算法 的优缺点

1、深度优先算法占内存少但速度较慢，广度优先算法占内存多但速度较快，在距离和深度成正比的情况下能较快地求出最优解。
2、深度优先与广度优先的控制结构和产生系统很相似，唯一的区别在于对扩展节点选取上。由于其保留了所有的前继节点，所以在产生后继节点时可以去掉一部分重复的节点，从而提高了搜索效率。
3、这两种算法每次都扩展一个节点的所有子节点，而不同的是，深度优先下一次扩展的是本次扩展出来的子节点中的一个，而广度优先扩展的则是本次扩展的节点的兄弟点。在具体实现上为了提高效率,所以采用了不同的数据结构。