알고리즘 분석 및 실례 해석(一)-분치법

분치법 (divide and conquer)
규모가 n인 문제에 대해 만약에 이 문제가 쉽게 해결될 수 있다면 직접 해결하고 그렇지 않으면 k개의 규모가 비교적 작은 자 문제로 분해한다. 이 자 문제들은 서로 독립적이고 원 문제의 형식과 같으며 귀속적으로 이 자 문제를 해결한 다음에 각 자 문제의 해를 합쳐서 원 문제의 해를 얻는다.이런 알고리즘 설계 전략을 분치 전략이라고 한다.
분치법은 각 층의 귀속에 세 가지 절차로 구성된다.

1) 구분(divide): 원문제를 약간의 규모가 작고 서로 독립적이며 원문제와 형식이 같은 자문제로 분해한다

2) 해결(conquer): 만약에 하위 문제의 규모가 비교적 작으면 직접 해답을 구하고, 그렇지 않으면 각 하위 문제를 차례로 해답을 구한다

3) 합병(combine): 각 하위 문제를 원래 문제의 해로 통합..

분치법에는 어떤 고전적인 예가 있습니까?그것은 정말 많다. 비교적 흔히 볼 수 있는 것은 아래에 일일이 열거하여 분석할 것이다.

이분법 찾기

이분법이 해결하는 기본적인 문제는 이미 알고 있는 n개의 서열에서 주어진 원소가 존재하는지 찾는 것이다.이분법의 기본 사상은 두 갈래로 나무를 찾는 구조에 쓰였다.

다음은 c++ 프로그램 코드입니다.

#include 
#include 
#include 
#include 
#include 
 
int * rand_seq(int num)// num 
{
	int *tem=new int[num]; 
	srand((unsigned)time(NULL));
	for(int i=0;i(std::cout," "));
	std::cout<<:endl int="" bin_search="" num="" key="" begin="0;" end="num-1;" while="" mid="(begin+end)/2;" if="" return="" else="" rec_bin_search="" null="" main="" argc="" char="" argv="" print_seq="" res="bin_search(data,20,data[2]);" std::cout="" success="" at=""/>

최대값과 최소값 찾기

문제 설명: n개의 서로 다른 원소의 집합에서 그것의 최대치와 최소치를 동시에 찾아낸다.

일반적인 역법으로 최악의 경우 비교 횟수는 2(n-1), 분치법 비교 횟수는 3n/2-2이다. 코드를 보면 다음과 같다.

#include 
#include 
#include 
#include 
#include 
#include 
 
int * rand_seq(int num)// num 
{
	int *tem=new int[num]; 
	srand((unsigned)time(NULL));
	for(int i=0;i(std::cout," "));
	std::cout<<:endl void="" rec_maxmin="" if="" res_max="res_min=*begin;" else="">*end)?(res_max=*begin,res_min=*end):
					  (res_max=*end,res_min=*begin);
	}else
	{
		int *mid=begin+(end-begin)/2;
		int lmax=INT_MIN,rmax=INT_MIN,lmin=INT_MAX,rmin=INT_MAX;
		rec_MaxMin(begin,mid,lmax,lmin);
		rec_MaxMin(mid+1,end,rmax,rmin);
		res_max=std::max(lmax,rmax);
		res_min=std::min(lmin,rmin);
	}
} 

int main(int argc, char** argv) 
{
	int *data=rand_seq(20);
	print_seq(data,20);
	// ，INT_MAX INT_MIN limits.h  
	int max=INT_MIN;
	int min=INT_MAX;
/*	std::cout<

제k 소원소 문제 구하기

이 문제는 최대치의 최소값을 구하는 문제에서 나온 것이다. 문제 설명: n개의 서로 다른 원소의 집합에서 그의 k소값을 찾아낸다.이 문제를 선택문제라고도 부른다.

당1

만약 빠른 정렬에서의 구분 방법을 사용한다면, 주원을 기준으로 한 표를 좌우 두 개의 하위 표로 구분한다.원표의 길이를 n으로 하고 한 차례의 구분을 거쳐 두 개의 좌우 자표로 나눈다고 가정한다. 그 중에서 왼쪽 자표는 주원과 왼쪽 원소의 자표이고 그 길이는 p, 오른쪽 자표는 주원의 오른쪽 원소의 자표이다.그러면 만약에 k==p라면 주원은 제k소원소이다.하면, 만약, 만약...

다음 두 가지 사고방식의 코드:

#include 
#include 
#include 
#include 
#include 
 
int * rand_seq(int num)// num 
{
	int *tem=new int[num]; 
	srand((unsigned)time(NULL));
	for(int i=0;i(std::cout," "));
	std::cout<<:endl void="" adjust_heap="" key="" num="" if="" int="" left="2*key+1;" right="2*key+2;" min_index="(data[key]">data[left])?((rightdata[right])?right:left):((rightdata[right])?right:key);
		if(min_index!=key)
		{
			std::swap(data[key],data[min_index]);
			adjust_heap(data,min_index,num);
		}	
	}
}
void build_heap(int *data,int num)
{
	int max_index=(num-1)/2;
	for(int i=max_index;i>=0;i--)
		adjust_heap(data,i,num);
}

int k_min_heap(int *data,int num,int k)
{
	build_heap(data,num);
	for(int i=1;item) --right;
			while((left

병합 정렬 & 빠른 정렬

이 두 가지 정렬 방법은 모두 정렬을 분리하는 대표적인 예이다. 특히 정렬을 병합하는 것은 분해, 정렬, 합병이다.

이 두 가지 방법에 대한 상세한 소개는 나의 또 다른 논문인 을 참고한다.