蛮力法和分治法的性能比较.doc

《蛮力法和分治法的性能比较.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、蛮力法与分治法求解最近对问题1、蛮力法蛮力法是一种简单直接地解决问题的方法，常常直接基于问题的描述和所涉及的概念定义，来求解问题。虽然巧妙和高效的算法很少来自于蛮力法，但它仍是一种重要的算法设计策略：（1）适用泛围广，是能解决几乎所有问题的一般性方法；（2）常用于一些非常基本、但又十分重要的算法（排序、查找、矩阵乘法和字符串匹配等）；（3）解决一些规模小或价值低的问题；（4）可以做为同样问题的更高效算法的一个标准；（5）可以通过对蛮力法的改进来得到更好的算法。2、分治法分治法，就是分而治之即把一个复杂的问题分成两个或更多的相同或

2、相似的子问题，再把子问题分成更小的子问题直到问题解决。分治法在求解问题时，效率比较高，也是一种重要的算法策略：（1）该问题的规模缩小到一定的程度就可以容易地解决；（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；（3）利用该问题分解出的子问题的解可以合并为该问题的解；（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。算法的基本思想及复杂度分析1．蛮力法（1）基本思想蛮力法求解最近对问题的过程是：分别计算每一对点之间的距离，然后通过排序找出距离最小的一对，为了避免对同一对点计

3、算两次距离，只考虑i

4、，关键问题是如何实现分治法中的合并步骤，如果组成S的最接近点对的2个点都在S1中或都在S2中，则问题很容易解决。但是，如果这2个点分别在S1和S2中，则对于S1中任一点p，S2中最多只有n/2个点与它构成最接近点对的候选者，仍需计算才能得到准确结果。（2）复杂度分析应用分治法求解含有n个点得最近对问题，其时间复杂性可由下面的递推式表示：T（n）=2T（n/2）+f(n)合并子问题的解的时间f（n）=O（1），由通用分治递推式的主定理可得：T（n）=O（nlogn)为提高算法效率，在算法中采用预排序技术，即在使用分治法之前，预先将

5、S中的n个点依其y坐标排序好。经过预排序处理后的算法所需的计算时间T(n)满足递归方程：当n小于4时，T(n)=O(1)；当n大于等于4时，T(n)=2T(n/2)+O(n)。由此易知，T(n)=O(nlogn)。预排序所需的计算时间显然为O(nlogn)。因此，整个算法所需的计算时间为O(nlogn)在点的个数比较少的时候，蛮力法所用时间比分治法少，点数比较多的情况下，分治法的优势就很明显了，所用时间明显比蛮力法少。算法描述（1）蛮力法在最近对问题中的算法描述程序：importjava.util.*;publicclassma

6、nlifa{publicstaticvoidmain(String[]args){Scannerin=newScanner(System.in);System.out.println("有多少对点需要比较?");intn=in.nextInt();int[]x=newint[n];10int[]y=newint[n];System.out.println("请输入这些点,横坐标:");for(inti=0;i

7、for(inti=0;i

8、);if(d