알고리즘 분할정복법 / 이분검색 / 합병정렬 / 퀵정렬

알고리즘 분할정복법 / 이분검색 / 합병정렬 / 퀵정렬 /

알고리즘 분할정복법 / 이분검색 / 합병정렬 / 퀵정렬 /

알고리즘 작성기법 (분할과 정복 divide and conquer) - 하향식 접근법

1. 분할정복법(이분검색-Binary Search / 합병정렬-Merge Sort / 빠른정렬-Quick Sort)

: 커다란 데이터가 있으면 한꺼번에 정복하기 어려우니 분할..분할..분할....정복

(Top Down방식 – 하향식 방법) (분할된 데이터를 - 재귀방법 사용)

1)이분검색 (정렬이 되있어야함) O(log n)

배열을 2개의 부분배열로 분할한다(Divide) 키값이 가운데 값보다 작으면 왼쪽 부분배열 선택, 크면 오른쪽 부분배열 선택 -> 선택한 부분배열에 킷값이 있는지 보고 없다면 재귀적인 방법으로(반복하여) 킷값을 결정할수 있도록 한다

이분검색 시간 복잡도는 O(logN)

N = 7억 인경우 최대 비교횟수는

= log₂ 700000000

2)합병정렬 (54p 55p표) 하나의 배열 -> 두 개의 정렬된 배열 -> 하나의 정렬된 배열로 합병

O(n logn)

3)퀵정렬 O(n제곱) (데이터가 정렬되있다면 퀵정렬은 별로임)

배열을 분할할 때 어떤 기준아이템(피봇 아이템)보다 작은 아이템들은 모두 그 앞부분에 위치시키고 기준아이템보다 크거나 같은 아이템들은 뒷부분에 위치시킨다. (편의상 첫 번째 아이템이 피봇 아이템이됨) - 그리고 나누어진 두 부분배열을 각각 재귀 호출하여 정렬함- 아이템이 하나뿐인 배열로 분할될 때까지 반복해서 나눔.

데이터가 많음-> 처리힘듬 -> 분할과 정복

-> 분할정복법이 힘든, 비효율적인 경우

1)크기 n인 사례가 거의 n에 가까운 크기의 2개 이상의 사례로 분할된다 ex)피보나찌

2)크기 n인 사례가 n/c 크기의 거의 n개 사례로 분할된다

피보나찌같이 작은 사례들이 서로 관련이 있는 문제를 풀때는 분할정복으로 하면 매우 비효율적이다. -> 작은사례를 먼저 해결하고 그 결과를 저장한다음 후에 그 저장한 결과를 이용하는 동적 계획법이 더 유용함. (동적계획법은 상향식 접근법)