(算法分析设计)第2章递归与分治策略课件.ppt

《(算法分析设计)第2章递归与分治策略课件.ppt》由会员分享，可在线阅读，更多相关《(算法分析设计)第2章递归与分治策略课件.ppt（84页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第2章 递归与分治策略第2章 递归与分治策略学习要点学习要点:n理解递归的概念。n掌握设计有效算法的分治策略。n通过下面的范例学习分治策略设计技巧。（1）二分搜索技术；（2）大整数乘法；（3）Strassen矩阵乘法；（4）合并排序（5）快速排序；（6）线性时间选择；学习要点:n将要求解的较大规模的问题分割成k个更小规模的子问题。算法总体思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n)=n对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。将要求解的较

2、大规模的问题分割成k个更小规模的子问题。算法总体(算法分析设计)第2章递归与分治策略课件(算法分析设计)第2章递归与分治策略课件2.1 递归的概念n直接或间接地调用自身的算法称为递归算法递归算法。用函数自身给出定义的函数称为递归函数递归函数。n由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子子问题与与原原问题类型一致而其型一致而其规模却不断模却不断缩小小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。n分治与递归像一对孪生兄弟，经常同时应用。2.1 递归的概念直接或间接地调用自身的算法称为递归算法。2.1 递归

3、的概念例例1 1 阶乘函数阶乘函数 非递归定义：非递归定义：n n！=n*(n-1)*(n-2)*1=n*(n-1)*(n-2)*1 阶乘函数可递归地定义为：边界条件边界条件递归方程递归方程边界条件与递归方程是递归函数的二个要素。2.1 递归的概念例1 阶乘函数边界条件递归方程边界条件n递归算法：int recur(int n)if(n=1)return 1;return n*recur(n-1);递归出口递归出口递归调用递归调用递归算法：递归出口递归调用2.1 递归的概念例例2 Fibonacci2 Fibonacci数列数列无穷数列1，1，2，3，5，8，13，21，34，55，称为Fib

4、onacci数列。它可以递归地定义为：边界条件边界条件递归方程递归方程第n个Fibonacci数可递归地计算如下：int fibonacci(int n)if(n 0)hanoi(n-1,a,c,b);move(a,b);hanoi(n-1,c,b,a);表示以塔座b为辅助塔座，将塔座上自下而上，由大到小叠在一起的-1个圆盘按规则移至塔座上并按同样顺序叠放。将塔座a上的圆盘移动到塔座b上去void hanoi(int n,int a,int bHanoi塔问题的复杂性分析n=1移动次数（）n移动次数（）n移动次数（）n移动次数（）n当时当时移动次数（）？移动次数（）？Hanoi塔问题的复杂性分

5、析=1递归小结优点：优点：结构清晰，可构清晰，可读性性强，而且容易用，而且容易用数学数学归纳法来法来证明算法的正确性，因此它明算法的正确性，因此它为设计算法、算法、调试程序程序带来很大方便。来很大方便。缺点：缺点：递归算法的运行效率算法的运行效率较低，无低，无论是是耗耗费的的计算算时间还是占用的存是占用的存储空空间都比都比非非递归算法要多。算法要多。递归小结优点：结构清晰，可读性强，而且容易用数学归纳法来证明n求Fibonacci数时有很多重复工作：求Fibonacci数时有很多重复工作：解决方法：解决方法：在在递归算法中消除算法中消除递归调用，使其用，使其转化化为非非递归算法。算法。1、采用

6、一个、采用一个用用户定定义的的栈来模来模拟系系统的的递归调用工作用工作栈。该方法方法通用性通用性强，但本，但本质上上还是是递归，只不，只不过人工做了本来由人工做了本来由编译器做的事情，器做的事情，优化效果不明化效果不明显。2、用、用递推推来来实现递归函数。函数。3、通、通过变换能能将一些将一些递归转化化为尾尾递归，从而，从而迭代求出迭代求出结果。果。后两种方法在后两种方法在时空复空复杂度上均有度上均有较大改善，大改善，但其适用范但其适用范围有限有限。递归小结解决方法：在递归算法中消除递归调用，使其转化为非递归算法。递分治法的基本思想n分治法的基本思想分治法的基本思想将一个规模为n的问题分解为a

7、个规模较小的子问题，这些子问题互相独立并且与原问题相同。通过递归地求解这些子问题，然后再将各个子问题的解合并，就可以实现对原问题的求解。分治法的基本思想分治法的基本思想分治法的求解过程分治法的求解过程分治法的求解过程n分解分解(divide)：将原问题分解为一系列子问题；：将原问题分解为一系列子问题；n递归求解递归求解(conquer)：递归求解各个子问题。若：递归求解各个子问题。若子问题足够小，则直接求解。子问题足够小，则直接求解。n合并合并(merge)：将子问题结果合并成原问题的解：将子问题结果合并成原问题的解说明：某些问题不需要说明：某些问题不需要合并合并，比如二分搜索，比如二分搜索问

8、题问题分治法的求解过程分治法的求解过程divide-and-conquer(P)if(|P|=n0)adhoc(P);divide P into smaller subinstances P1,P2,Pa;for(i=1,i=a,i+)yi=divide-and-conquer(Pi);return merge(y1,y2,ya);|P|：问题P的规模；adhoc：分治法中的基本子运算n0：阀值如果问题P的规模不超过n0，说明问题已经容易求解，不要再继续分解。利用adhoc(P)直接求解。分治法的设计模式divide-and-conquer(P)|P|：问题P的规分治法的分割原则n分治法的分割

9、原则分治法的分割原则实践实践表明：将一个问题划分成数据规模大小相数据规模大小相等的等的a个子问题个子问题的处理方法行之有效；分治法的分割原则分治法的分割原则分治法的计算效率分析n分治法的计算效率分析分治法的计算效率分析通常用递归方程来进行分析通常用递归方程来进行分析分治法将规模为n的问题分成a个规模为n/b的子问题n设分解阈值n0=1，且adhoc解规模为1的问题耗费1个单位时间n设将原问题分解为a个子问题以及用merge将a个子问题的解合并为原问题解需要使用f(n)个单位时间。n用T(n)表示该分治法divide-and-merge(P)解规模为|P|=n的问题所需要的计算时间分治法的计算效

10、率分析分治法的计算效率分析(算法分析设计)第2章递归与分治策略课件g(n)函数函数g(n)函数g(n)函数g(n)函数T(n)函数g(n)函数g(n)函数T(n)函数主方法(详见算法导论)根据这两项对结果的影响不同，分成三种情况讨论主方法(详见算法导论)根据这两项对结果的影响不同，分成三(算法分析设计)第2章递归与分治策略课件因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征。这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心算法贪心

11、算法或动态规划动态规划。这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划动态规划较好。分治法的适用条件分治法所能解决的问题一般具有以下几个特征：分治法所能解决的问题一般具有以下几个特征：分治法所能解决的问题一般具有以下几个特征：分治法所能解决的问题一般具有以下几个特征：n该问题的的规模模缩小到一定的程度就可以容易地解决；小到一定的程度就可以容易地解决；n该问题可以分解可以分解为若干个若干个规模模较小的相同小的相同问题，即，即该问题具有具有最优子结构性质最优子结构性质n利用利用该问题分解出的子分解出的子

12、问题的解可以合并的解可以合并为该问题的的解；解；n该问题所分解出的各个子所分解出的各个子问题是是相互独立相互独立的，即子的，即子问题之之间不包含公共的子不包含公共的子问题。因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部n二分搜索技术n大整数的乘法nStrassen矩阵乘法n合并排序n快速排序n线性时间选择二分搜索技术二分搜索技术二分搜索技术二分搜索技术分析：如果n=1即只有一个元素，则只要比较这个元素和x就可以确定x是否在表中。因此这个问题满足分治法的第一个适用条件分析：比较x和a的中间元素amid，若x=amid，则x在L中的位置就是mid；如果xai，同理我们只要在amid的

13、后面查找x即可。无论是在前面还是后面查找x，其方法都和在a中查找x一样，只不过是查找的规模缩小了。这就说明了此问题满足分治法的第二个和第三个适用条件。分析：很显然此问题分解出的子问题相互独立，即在ai的前面或后面查找x是独立的子问题，因此满足分治法的第四个适用条件。二分搜索技术给定已按升序定已按升序排好序排好序的的n个元素个元素a0:n-1，现要在要在这n个元素中找个元素中找出一特定元素出一特定元素x。分析：分析：该问题的的规模模缩小到一定的程度就可以容易地解决；小到一定的程度就可以容易地解决；该问题可以分解可以分解为若干个若干个规模模较小的相同小的相同问题;分解出的子分解出的子问题的解可以合

14、并的解可以合并为原原问题的解；的解；分解出的各个子分解出的各个子问题是相互独立的。是相互独立的。分析：如果n=1即只有一个元素，则只要比较这个元素和x就可以n逐个地扫描数组a中每个元素，直到找到x为止。在含有n个元素的线性表中查找一个元素在最坏情况下都需要进行n次比较，其时间复杂度为O(n)。n利用分治法分治法求解此问题,求解过程是：将n个元素分分成个数大致相等彼此独立的两半部分，分，即an/2的前面或后面两个子问题；将第n/2位置的元素与x进行比较，如果相等，则找到x，算法结束。如果xan/2,则在数组a的后半部分分继续搜索搜索x；如果xan/2,则在数组a的前半部分分继续搜索搜索x。逐个地

15、扫描数组a中每个元素，直到找到x为止。二分搜索技术给定已按升序排好序的定已按升序排好序的n个元素个元素a0:n-1，现要在要在这n个元素中找个元素中找出一特定元素出一特定元素x。据此容易设计出二分搜索算法二分搜索算法：template int BinarySearch(Type a,const Type&x,int l,int r)while(r=l)int m=(l+r)/2;if(x=am)return m;if(x am)r=m-1;else l=m+1;return-1;算法复杂度分析：算法复杂度分析：每执行一次算法的while循环，待搜索数组的大小减少一半。因此，在最坏情况下，whi

16、le循环被执行了O(logn)次。循环体内运算需要O(1)时间，因此整个算法在最坏情况下的计算时间复杂性为O(logn)。二分搜索技术给定已按升序排好序的n个元素a0:n-1，现大整数的乘法大整数的乘法大整数的乘法大整数的乘法n大整数的乘法大整数的乘法问题描述n需要处理的整数超过了计算机硬件能直接处理的整数范围n浮点数计算对精度的影响解决方案n利用软件方法来实现大整数的乘法典型应用nRSA密码体系大整数的乘法大整数的乘法 n传统做法：需要做n*n次1位整数乘法操作，n-1次移位操作，n-1次加法操作时间复杂度为O(n2)传统做法：n/2位n/2位ABX=n/2位n/2位CDY=大整数大整数X和

17、和Y的分段的分段X、Y为两个为两个n位的二进制整数位的二进制整数n/2位n/2位ABX=n/2位n/2位CDY=大整数X和YXY的乘积形式（1/2）形式一：形式一：包括：包括：4次次n/2位整数的乘法位整数的乘法3次不超过次不超过2n位的整数加法位的整数加法2次移位次移位XY的乘积形式（1/2）形式一：包括：所有加法和移位共用所有加法和移位共用O(n)步运算步运算设设T(n)是是2个个n位整数相乘所需的运算总数位整数相乘所需的运算总数所有加法和移位共用O(n)步运算XY的乘积形式（2/2）形式二：形式二：包括：包括：3次次n/2位整数的乘法位整数的乘法6次整数加、减法次整数加、减法2次移位次移

18、位XY的乘积形式（2/2）形式二：包括：p如果将大整数分成更多段，用更复杂的方式把它们组合起来，将有可能得到更优的算法。p最终的，这个思想导致了快速傅利叶变换快速傅利叶变换(Fast Fourier Transform)的产生。该方法也可以看作是一个复杂的分治算法，对于大整数乘法，它能在O(nlogn)时间内解决。p是否能找到线性时间的算法？目前为止还没有结果。如果将大整数分成更多段，用更复杂的方式把它们组合起来，将有可StrassenStrassen矩阵乘法矩阵乘法Strassen矩阵乘法矩阵的乘法：矩阵的乘法：矩阵的乘法：(算法分析设计)第2章递归与分治策略课件Strassen矩阵乘法使用

19、与上例类似的技术，将矩阵A，B和C中每一矩阵都分块成4个大小相等的子矩阵。由此可将方程C=AB重写为：u传统方法：O(n3)u分治法:由此可得：复杂度分析复杂度分析T(n)=O(n3)2个n阶矩阵的乘积转化为计算8个n/2阶矩阵的乘积和4个n/2阶矩阵的和。2个(n/2)*(n/2)阶的矩阵加法可以在O(n2)时间内完成Strassen矩阵乘法使用与上例类似的技术，将矩阵A，B和Strassen矩阵乘法使用与上例类似的技术，将矩阵A，B和C中每一矩阵都分块成4个大小相等的子矩阵。由此可将方程C=AB重写为：u传统方法：O(n3)u分治法:由此可得：Strassen矩阵乘法使用与上例类似的技术，

20、将矩阵A，B和Strassen矩阵乘法u传统方法：O(n3)u分治法:为了降低时间复杂度，必须减少乘法的次数。复杂度分析复杂度分析T(n)=O(nlog7)=O(n2.81)较大的改大的改进做了7次乘法运算；做了18次加减法运算；Strassen矩阵乘法传统方法：O(n3)为了降低时间复杂u分解：将n阶矩阵A、B分解为n/2阶子矩阵；u解决：进行7次递归计算(n/2)*(n/2)子矩阵的乘积；u合并：按C的子矩阵，对子矩阵的乘积进行加减法运算；Strassen分治策略分解：将n阶矩阵A、B分解为n/2阶子矩阵；StrassenStrassen矩阵乘法u更快的方法?Hopcroft和Kerr已经

21、证明(1971)，计算2个矩阵的乘积，7次乘法是必要的。因此，要想进一步改进矩阵乘法的时间复杂性，就不能再基于计算22矩阵的7次乘法这样的方法了。或许应当研究或矩阵的更好算法。在Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。目前最好的计算时间上界是 O(n2.376)是否能找到O(n2)的算法？Strassen矩阵乘法更快的方法?Hopcroft和Ke合并排序合并排序合并排序合并排序基本思想：基本思想：将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。void mergesort(Type a,int lef

22、t,int right)if(leftright)/至少有2个元素 int i=(left+right)/2;/取中点 mergesort(a,left,i);mergesort(a,i+1,right);merge(a,b,left,i,right);/合并到数组b copy(a,b,left,right);/复制回数组a merge和copy可以在O(n)时间内完成，复杂度分析复杂度分析T(n)=O(nlogn)渐近意义下的最优算法算法mergesort递归地调用自身，不断将子序列分成两个更小的子序列算法merge合并两个排好序的数组到新数组b中算法copy将合并后的数值段再复制到数组a中

23、合并排序基本思想：将待排序元素分成大小大致相同的2个子集合，改进合并排序算法n算法mergesort存在递归过程p它将序列一分为二，直到序列只剩一个元素为止，然后不断合并2个排好序的序列；n改进思路：p将初始序列看出n个长度为1的有序子序列，然后两两归并，得到n/2个长度为2的有序子序列；再两两归并，重复直到得到一个长度为n的有序序列改进合并排序算法算法mergesort存在递归过程改进合并排序算法mergesort的递归过程可以消去。初始序列49 38 65 97 76 13 2738 49 65 97 13 76 27第一步第二步38 49 65 97 13 27 76第三步13 27 3

24、8 49 65 76 97改进合并排序算法mergesort的递归过程可以消去。初始序n自然合并排序算法：自然合并排序算法：任何数组都有现成已排好任何数组都有现成已排好序的子数组段，以此为基础排序序的子数组段，以此为基础排序4,8,3,7,1,5,6,2先进行一次线性扫描，再合并相邻排好的子数组段先进行一次线性扫描，再合并相邻排好的子数组段自然合并排序算法：任何数组都有现成已排好序的子数组段，以此为快速排序快速排序快速排序基本思想：基本思想：以以ap为基准元素，将数基准元素，将数组ap:r划分划分为ap:q-1小小,aq和和aq+1:r大大三段三段,然后通然后通过递归调用分用分别对ap:q-1

25、和和aq+1:r进行快速排序。行快速排序。说明：因排序分明：因排序分块进行，合并步行，合并步骤省略。省略。基本思想：以ap为基准元素，将数组ap:r划分为atemplate QuickSort(Type a,int p,int r)if(p=r)return;q=Partition(a,p,r);QuickSort(a,p,q-1);/对左半段排序对左半段排序QuickSort(a,q+1,r);/对右半段排序对右半段排序template 在在Partition(a,p,r)中，中，记录的比的比较和和交交换是是从两端向中从两端向中间进行的行的,值较大的大的记录交交换到到aq+1,r，值较小的小

26、的记录交交换到到ap,q-1。记录每次移每次移动的距离的距离较大，但大，但总的比的比较和移和移动次数次数较少。少。在Partition(a,p,r)中，记录的比较和交换prr23p80r14p52例如：例如：ap=52prrrpprr23p80r14p52例如：ap=52prrrptemplate Type Partition(Type a,int p,int r)Type x=ap;while(pr)while(p=x)-r;ap=ar;while(pr&ap=x)+p;ar=ap;ap=x;return p;/返回枢轴所在位置/Partitiontemplate 基准元素基准元素快速排序算

27、法的复杂性分析n快速排序算法的复杂性分析快速排序算法的复杂性分析运行时间与划分是否对称有关n最坏情况：最坏情况：对于一个包含n个元素的数组，被划分成两个区域，其中一个包含n-1个元素，而另一个中只有一个元素。n最好情况：最好情况：每次划分都产生两个大小为n/2的区域。快速排序算法的复杂性分析快速排序算法的复杂性分析 快速排序算法在最好情况下的时间复杂性是快速排序算法在最好情况下的时间复杂性是O(nlogn)通常基于比较的排序算法的算法复杂度是通常基于比较的排序算法的算法复杂度是O(n2)快速排序算法因此得名，对规模大的问题较有效快速排序算法因此得名，对规模大的问题较有效算法设计者因为这个代表性

28、贡献而获得算法设计者因为这个代表性贡献而获得1980年的年的Turing奖奖 快速排序算法在最好情况下的时间复杂性是O(nlogn)templateint RandomizedPartition(Type a,int p,int r)int i=Random(p,r);Swap(ai,ap);return Partition(a,p,r);快速排序算法的性能取决于划分的对称性。通过修改算法partition，可以设计出采用随机选择策略的快速排序算法。在快速排序算法的每一步中，当数组还没有被划分时，可以在ap:r中随机选出一个元素作为划分基准，这样可以使划分基准的选择是随机的，从而可以期望划分是

29、较对称的。&最坏最坏时间复复杂度：度：O(n2)&平均平均时间复复杂度：度：O(nlogn)&辅助空助空间：O(n)或或O(logn)template 快速排序算法线性时间选择线性时间选择线性时间选择线性时间选择的基本思想n元素选择问题元素选择问题给定线性序集中的给定线性序集中的n个元素和一个整数个元素和一个整数k，1kn，要求找出，要求找出这n个元素中第个元素中第k小的元素。小的元素。n当k=1时找最小元素；n当k=n时找最大元素；n当k=(n+1)/2找中位数n算法算法设计思想思想与快速排序算法的设计思想基本相同，即对输入数组进行递归划分，但操作上操作上只只对划分出的两个划分出的两个子数子

30、数组中的一个中的一个进行行进一步的一步的递归处理理；线性时间选择的基本思想元素选择问题Type RandomizedSelect(Type a,int p,int r,int k)if(p=r)return ap;int i=RandomizedPartition(p,r);/将数组划分为两部分 int j=i-p+1;/ap:i的元素个数 if(k=j)return RandomizedSelect(a,p,i,k);else return RandomizedSelect(a,i+1,r,k-j);说明：为什么只需要对其中的一个子数组进行进一步的递归处理为什么只需要对其中的一个子数组进行进

31、一步的递归处理数组ap:r被划分成两个子数组ap:i和ai+1:r,使得ap:i中的元素都不大于ai+1:r中的元素；计算ap:i中的元素个数j，如果kj,则所要找的元素就在ap:i内，否则在ai+1:r内只要对其中的一个子数组进一步的递归处理即可Type RandomizedSelect(Type atemplateRandomizedPartition(Type a,int p,int r)int i=rand()%(r-p+1)+p;Swap(ai,ap);return Partition(a,p,r);template Type Partition(Type a,int p,int r

32、)int i=p,j=r+1;Type x=ap;while(true)while(a+ix&ix);if(i=j)break;Swap(ai,aj);ap=aj;aj=x;return j;template对算法的讨论nRandomizedSelect算法在最坏情况下需要(n2)计算时间，其平均计算时间为O(n)n出发点：出发点：如果能在线性时间内找到一个划分基准，使得使得按这个基准所划分出的两个子数组的长度都至按这个基准所划分出的两个子数组的长度都至少为原数组的少为原数组的倍（倍（0011），那么就可以在最坏的情况下用O(n)时间完成选择任务对算法的讨论RandomizedSelect算法

33、在最坏情况下说明说明寻找满足要求的划分基准n按以下步骤寻找满足要求的划分基准按以下步骤寻找满足要求的划分基准1.将n个输入元素划分成n/5个组，每组5个元素，只可能有一个组不是5个元素。用任意一种排序算法对每组中的元素进行排序，并取出每组中的中位数，共n/5个。2.递归调用算法select来找这n/5个元素的中位数。如果n/5个为偶数，就找它的两个中位数中较大的一个。以这个元素作为划分基准。注：注：假定假定n个元素都互不相等个元素都互不相等寻找满足要求的划分基准按以下步骤寻找满足要求的划分基准注：假x选择划分基准选择划分基准x选择划分基准分析满足算法满足算法select的要求的要求分析满足算法

34、select的要求算法复杂性分析按算法所选基准x进行划分所得到的2个子数组分别至多有3n/4个元素，无论对哪一个子数组调用select都至多用T(3n/4)的时间找中位数的中位数算法复杂性分析按算法所选基准x进行划分所得到的2个子数组分别分析n分析分析Select算法将每一组的大小定为5，并选取75作为是否进行递归调用的分界点。这两点保证了T(n)的递归式中两个自变量之和n/5+3n/4=19n/20=an,0a1使T(n)=O(n)的关键*除5和75的组合之外，还有其他选择分析分析Type Select(Type a,int p,int r,int k)if(r-p75)/75为事先设定的阈

35、值为事先设定的阈值 用某个简单排序算法对数组用某个简单排序算法对数组ap:r排序排序;return ap+k-1;for(int i=0;i=(r-p-4)/5;i+)将将ap+5*i至至ap+5*i+4的第的第3小元素与小元素与ap+i交换位置交换位置;/找中位数的中位数，找中位数的中位数，r-p-4即上面所说的即上面所说的n-5 Type x=Select(a,p,p+(r-p-4)/5,(r-p-4)/10);int i=Partition(a,p,r,x),j=i-p+1;if(k=j)return Select(a,p,i,k);else return Select(a,i+1,r,

36、k-j);Type Select(Type a,int p,考虑存在相等元素的问题Type Comparable select(int p,int r,int k)Comparable x=select(p,p+(r-p-4)/5,(r-p+6)/10);int i=patition(p,r,x),j=i-p+1;*对所有等于基准对所有等于基准x的相等元素进行汇总的相等元素进行汇总;如果如果(个数个数m1，且，且jkj+m-1)直接返回直接返回ai;否则否则 调用调用select(i+m+1,r,k-j-m);*考虑存在相等元素的问题Type Comparable sel实验题：1、算法分析题

37、2-5 2、线性时间选择（分治策略）实验数据：input.txt（共100个数据）要求找出序列中最小的元素将最小元素输出到output.txt文件中 实验题：1、算法分析题2-5 3、主元素问题主元素问题n问题描述：问题描述：设T0:n-1是n个元素的数组，如果其中某个元素x在整个数组中的出现次数超过n/2，则称x为数组T的主元素。输入数据由文件名为input.txt的文本文件提供。n请设计一个线性时间算法，判断input中的数据是否存在主元素。在实验报告中对算法时间复杂度作出分析。n输入：文件的第1行为数组S中元素个数n；接下来的n 行中，每行有一个自然数。程序运行结束时，将计算结果输出到文件output.txt中。输出文件中包含问题的答案：找不到主元素时给出null，找到时给出主元素的值。3、主元素问题理论作业n算法分析题n2-4、2-9、2-11、2-12理论作业算法分析题