리포트 논문 자기소개서 이력서 시험자료 서식 PPT양식 표지/속지
SiteMap
평가점수C

알고리즘 기초 분할정복 연습문제 레포트

저작시기 2015.05 |등록일 2015.07.13 | 최종수정일 2016.09.08 한글 (hwp) | 8페이지 | 가격 1,000원

소개글

출판사 : 홍릉과학출판사
저자 : Richard Neapolitan
역자 : 도경구

연습문제 레포트 입니다.
윈도우 7 , visual studio 2013

본문내용

2. 좀 비현실적이기는 하지만 이분검색(알고리즘 2.1) 알고리즘을 사용하여 원소가 7억 개인 배열을 검색한다고 가정해보자. 특정 원소를 찾기 위해서 비교를 최대로 몇 번해야 할까? 특정 원소가 배열에 있을 수도 있고 없을 수도 있다.
- 알고리즘 2.1을 사용하였다 는 것으로 보아 배열이 정렬 되었다고 가정한다.
워스트 케이스로 계산시 W(n) = lg(n)의 하한 + 1 이므로
lg9억 = 29.7453497605 이기 때문에 하한은 29 이고 +1 을 해주면 30 이다.
결국 최대 30번의 수행을 하면 된다.
결론 : 이진탐색은 정렬된 배열에서 아주 좋은 효율을 보여준다.

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

참고 자료

없음
다운로드 맨위로