검색어 입력폼
평가점수C

[컴퓨터 알고리즘]알고리즘 연습문제 2장

등록일 2004.03.21 | 최종수정일 2015.10.06 한글파일한글 (hwp) | 4페이지 | 가격 2,500원

소개글

열심히 공부하세요

목차

2.1 이분검색 (알고리즘2.1)을 사용하여 다음 정수 리스트(배열)에서 120을 검색하라. 알고리즘이 진행되는 과정을 단계별로 보여라.
2.3 검색이 항상 성공한다고 가정해보자. 즉, 그렇게 되면 알고리즘 2.1에서 아이템 x는 리스트 S에서 항상 찾을 수 있다. 불필요한 연산을 제거하여 알고리즘 2.1을 개선하라.
2.5 알고리즘 2.1(4번째 줄)에서 분할 함수가 mid=low; 로 바뀌었다고 하자. 새 검색전략을 설명하라. 그리고 이 전략의 성능을 분석하고 결과를 차수표기법으로 표시하라.
2.7 분할정복법을 사용하여 n개 아이템의 리스트에서 가장 큰 아이템을 찾는 알고리즘을 작성하라. 이 알고리즘을 분석하고 결과를 차수표기법으로 표시하라.
2.9 연습문제 8에서 재귀 호출 트리를 구축하라
2.13 n개의 아이템으로 구성된 리스트를 크기가 거의 n/3인 3개의 부분리스트로 분할하고 , 각 부분 리스트를 재귀적으로 정렬한 후, 그 3개의 정렬된 부분리스트를 합병하는 정렬 알고리즘을 작성하라. 작성한 알고리즘을 분석하고 , 결과를 차수 표기법으로 표시하라.
2.17 하노이탑문제를 푸는 분할정복 알고리즘을 작성하라.
2.19 빠른 정렬을 사용하여 다음 리스트를 정렬하라. 알고리즘이 진행되는 과정을 단계별로 보여라,
2.21 다음 등식을 성립함을 보여라.

본문내용

2.1 이분검색 (알고리즘2.1)을 사용하여 다음 정수 리스트(배열)에서 120을 검색하라. 알고리즘이 진행되는 과정을 단계별로 보여라.

12 34 37 45 57 82 99 120 134
1. 이중에서 가운데수는 57이다.
12 34 37 45
2. 이것을 먼저 검색한다.
82 99 120
3. 위에서 없었으므로 82 99 120 순으로 검색하여 120을 찾아낸다.

2.3 검색이 항상 성공한다고 가정해보자. 즉, 그렇게 되면 알고리즘 2.1에서 아이템 x는 리스트 S에서 항상 찾을 수 있다. 불필요한 연산을 제거하여 알고리즘 2.1을 개선하라.

알고리즘의 검색이 처음에 모두 성공하게 된다면 이 뒷부분은 모두 필요치 않게 된다.
이 부분을 삭제하여도, 검색이 모두 처음에 성공한다면 무리없이 돌아가는 알고리즘이 된다.
else if (x<S[mid])
return location (low , mid -1);
else
return location (mid +1,high);
다운로드 맨위로