首页 > 代码库 > 算法笔记04--分治法之寻找最大最小元素
算法笔记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--分治法之寻找最大最小元素
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。