算法笔记04--分治法之寻找最大最小元素

顾名思义，“分治”名字本身就已经给出了一种强有力的算法设计技术，它可以用来解决各类问题。在它最简单的形式里，一个分治算法把问题实例划分成若干子实例（多数情况是分成两个），并分别递归地解决每个子实例，然后把这些子实例的解组合起来，得到原问题实例的解。

寻找最大最小解

一种直接的算法如下所示，它返回一个数对(x,y)，其中x是最小值，y是最大值

1 x<-A[1] ; y<-A[1]

2 for i <- 2 to n

3        if A[i] < x then x <- A[i]

4        if A[i] > y then y <- A[i]

5 end for

6 return (x,y)  

很显然执行次数为2*n-2

下面使用分治策略。

思路：

将数组分割成两半子实例，递归的在每一个子实例中找到最大值和最小值，然后将两个子实例的最小值中的最小值和最大值中的最大值返回。

时间复杂度：

C(n) = 1, n=2

C(n) = 2*C(n/2) + 2 , n>2

假设n = 2^k , k = log n

C(n) = 2*C(n/2) +2 

        = 2*(2*C(n/4) +2 ) + 2

.....

        = 2^(k-1)*C(n/2^(k-1)) + 2^(k-1) + 2^(k-2) + + 2^2 + 2

= 2^(k-1)*(C(2)) + 2^k - 2

= 3n/2 - 2

代码：

#include<iostream>
using namespace std;
int A[8] = {5,-3,2,7,10,1,2,-8};
struct minmaxV
{
int maxV;
int minV;
};
minmaxV minmax(int low , int high)
{
minmaxV temp,temp1,temp2,temp3;
if(high - low==1)
{
if(A[low]<A[high])
{
temp.minV = A[low];
temp.maxV = A[high];
}
else
{
temp.minV = A[high];
temp.maxV = A[low];
}
return temp;
}
else
{
int mid = (low + high) /2 ;
temp1 = minmax(low,mid);
temp2 = minmax(mid+1 , high);
temp3.minV = (temp1.minV<temp2.minV)?temp1.minV:temp2.minV;
temp3.maxV = (temp1.maxV>temp2.maxV)?temp1.maxV:temp2.maxV;
return temp3;
}
}
int main()
{
minmaxV showMinMax;
showMinMax =
minmax(0,7);
cout<<"min: "<<showMinMax.minV<<"
max: "<<showMinMax.maxV<<endl;
return 1;
}

最后

以上就是神勇小蝴蝶为你收集整理的算法笔记04--分治法之寻找最大最小元素的全部内容，希望文章能够帮你解决算法笔记04--分治法之寻找最大最小元素所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。