728x90
분할정복(Divide-and-Conquer)식 설계 전략
- 분할(Divide): 해결하기 쉽도록 문제를 여러 개의 작은 부분으로 나눈다.
- 정복(Conquer): 나눈 작은 문제를 각각 해결한다.
- 통합(Combine): (필요하다면) 해결된 해답을 모은다.
이러한 문제 해결 방법을 하향식(top-down) 접근방법이라고 한다.
이분검색(binary search): 재귀적 방식
- 문제: 크기가 n인 정렬된 배열 S에 x가 있는지를 결정하라.
- 입력: 자연수 n, 비내림차순으로 정렬된 배열 S[1..n], 찾고자 하는 항목 x
- 출력: location, x가 S의 어디에 있는지의 위치. 만약 x가 S에 없다 면 0
- 설계전략:
- x가 배열의 중간에 위치하고 있는 항목과 같으면, x 찾음. 그렇 지 않으면:
- 분할: 배열을 반으로 나누어서 x가 중앙에 위치한 항목보다 작 으면 왼쪽에 위치한 배열 반쪽을 선택하고, 그렇지 않으면 오 른쪽에 위치한 배열 반쪽을 선택한다.
- 정복: 선택된 반쪽 배열에서 x를 찾는다.
- 통합: (필요 없음)
이분검색(Binary Search): 재귀 알고리즘
Discussion
1. 입력 파라미터 n, S, x는 알고리즘 수행 중 변하지 않는 값이다. 따라서 함수를 재귀호출(recursive call)할 때 마다 이러한 변하지 않는 파라미터 를 가지고 다니는 것은 극심한 낭비이다. 따라서 n, S, x를 전역(global) 변수로 지정하고, 재귀호출에는 인덱스만 넘겨 줌
2. 재귀 알고리즘(recursive algorithm)에서 모든 재귀호출이 알고리즘의 마 지막(꼬리) 부분에서 이루어 질 때 꼬리 재귀호출(tail recursion)이라고 함
- 그 알고리즘은 반복 알고리즘(iterative algorithm)으로 변환하기가 수 월하다. 일반적으로 재귀 알고리즘은 재귀 호출할 때마다 그 당시의 상태를 활성 레코드(activation records) 스택에 저장해 놓아야 하는 반면, 반복 알고리즘은 그럴 필요가 없기 때문에 일반적으로 더 효율 적이다(빠르다). 그렇다고 반복 알고리즘의 계산복잡도가 재귀 알고 리즘보다 좋다는 의미는 아니다. 반복 알고리즘이 상수적(constant factor)으로만 좋다(빠르다)는 말이다.
최악의 경우 시간복잡도 분석
- 단위연산: x와 S[mid]의 비교
- 입력 크기: 배열의 크기 n (= high - low + 1)
- 단위연산으로 설정한 조건 문을 2번 수행하지만, 사실상 비교는 한번 이루 어진다고 봐도 된다. 그 이유는:
(1) 어셈블리 언어로는 하나의 조건 명령으로 충분히 구현할 수 있기 때 문이기도 하고;
(2) x를 찾기 전까지는 항상 2개의 조건 문을 수행하므로 하나로 묶어서 한 단위로 취급을 해도 되기 때문이기도 하다. 이와 같이 단위연산 은 최대한 효율적으로(빠르게) 구현된다고 일반적으로 가정하여, 1 단위로 취급을 해도 된다.
728x90
'👨💻Computer Science > 알고리즘 분석' 카테고리의 다른 글
[알고리즘 분석] 02 - 3 빠른정렬(Quicksort) (0) | 2021.09.23 |
---|---|
[알고리즘 분석] 02 - 2 합병정렬(mergesort) (0) | 2021.09.16 |
[알고리즘 분석] 01 - 3 차수(order) (0) | 2021.09.14 |
[알고리즘 분석] 01 - 2 알고리즘의 분석(analysis) (0) | 2021.09.14 |
[알고리즘 분석] 01 - 1 알고리즘: 효율, 분석 그리고 차수 (0) | 2021.09.02 |
댓글