算法设计与分析（第一篇）（分治与递归）（二分查找）在n+logn-2次比较中找出a[n]的最大元素与次大元素

在n+logn-2次比较中找出a[n]的最大元素与次大元素

●    算法思想

1)采用分治法将数组A[0:n]分成两部分，A[0:n/2-1]和A[n/2:n-1]

2) 对从i=0到n/2-1

    A[i]>A[i+n/2] 将A[i]和A[i+n/2]交换

3） 数组A[n/2:n-1]的大小>2, 则递归地进行分治法求出最大值和次最大值。

数组A[n/2:n-1]的大小<=2，则直接求出最大值和次最大值。

假设最大值为A[p]，次最大值A[q]

4)  原问题的最大值为A[p]

    原问题的次最大值为A[p-n/2]和A[q]的较大者

#include<stdio.h>
void Search(int a[],int *pmax,int *psecond,int left,int right);
int main()
{
	int pmax,psecond,left=0,right=19;
	int a[20]={-15,-6,-3, -1, 0,2,4,6,7,8,9,10,12,14,15,18,20,21,24,30};
	Search(a,&pmax,&psecond,left,right);
	printf("%d,%d ",a[pmax],a[psecond]);
	return 0;
 } 
void Search(int a[],int *pmax,int *psecond,int left,int right)
{
   	int i;
	if(left==right)
	{
		*pmax=*psecond=left;
	}
	else if(left==right-1)
	{
		if(a[left]>a[right])
		{
			*pmax=left;
			*psecond=right;
		}
		else
		{
			*pmax=right;
			*psecond=left;
		}
	}
	else
	{
		int m=(right-left+1)/2;	
		for(i=left;i<left+m;i++)
		{ 
			if(a[i]>a[i+m])
			{
				int temp=a[i];
				a[i]=a[i+m];
				a[i+m]=temp;
			}
		}	
		Search(a,pmax,psecond,left+m,right);
        if(a[*pmax-m]>a[*psecond]) 
			*psecond=*pmax-m;
	}
	
}

●    时间复杂性

当n是2的幂时(n=2^k),有，

T(n)=T(n/2) +n/2+1  n>2

        =1              n=2

        =0              n=1

上式展开：

 T(n)=T(n/2) +n/2+1

      =T(n/4) + n/4 + n/2+2

      =T(n/8) + n/8  +n/4 + n/2+3    

=…

= T(2)+2+ 2² +…+2² + 2^k-1+k-1

      =1+2+ 2² +…+2² + 2^k-1+k-1

      =2^k-1+k-1 =n+logn-2