알고리즘 2장 분할정복 연습문제

소개글

"알고리즘 2장 분할정복 연습문제"에 대한 내용입니다.

목차

없음

본문내용

2. 좀 비현실적이기는 하지만 이분검색(알고리즘 2.1) 알고리즘을 사용하여 원소가 7억 개인 배열을 검색한다고 가정해보자. 특정 원소를 찾기 위해서 비교를 최대로 몇 번해야 할까? 특정 원소가 배열에 있을 수도 있고 없을 수도 있다.

=> 알고리즘 2.1 의 재현식은 W(n) = +1 이므로 lg700000000 = 29.382779681156503 이고 하한은 29이므로 +1 해주면 30이다. 따라서 최대 30번의 수행을 하면 된다.

<중 략>

6. 원소가 n개인 정렬된 배열을 원소가 n/3개인 배열 3개로 분할(즉, 거의 같은 크기로 분할) 하여 검색하는 알고리즘을 작성하시오. 이 알고리즘은 분할한 세 배열 중에서 찾을 원소가 있을만한 배열에서 원소를 검색하는데, 이 배열을 다시 거의 같은 크기의 배열 3개로 분할한다. 원소를 찾거나, 원소가 배열에 없음이 확실할 때까지 이 과정을 뒤풀이한다. 이 알고리즘을 분석하고, 분석결과를 차수 표기법으로 답하시오.

=> int low = 0, high = n, S[n];
mergesort(int low, int high, int S[])
{
int onebythree = (low + high) / 3;
int twobythree = (low + high) * 2 / 3;
mergesort(low , onebythree,S);
mergesort(onebythree +1 , twobythree, S);
mergesort(twobythree +1 , high, S);
merge(low, onebythree, twobythree, high, S);
}
merge(int low, int onebythree, int twobythree, int high,int S[])
{
int i,j,k,l;
int B[high];
i = low; j= onebythree+1; k=twobythree+1; z=0;
while(i <= onebythree && j <= twobythree && k <= high) {
if(S[i] < S[j] && S[i] < S[k]) {
B[z] = S[i];
i++;

참고 자료

없음