4강 제2장 분할정복 알고리즘 2

2.3 합병 정렬

 

2.3.1 개념과 원리

합병 정렬 ( merge sort ) 

전형적인 분할정복 방법에 해당

배열을 동일한 크기의 두 개의 부분배열로 분할하고, 각각의 부분배열을 순환적으로 정렬한 후,

정렬된 두 부분배열을 합병하여 하나의 정렬된 배열을 만듦

 

분할 : 입력 크기 n인 배열을 크기 n/2인 두 부분배열로 분할

정복 : 각 부분배열에 대해서 합병 정렬을 순환적으로 적용하여 두 부분배열을 정렬

결합 : 정렬된 두 부분배열을 합병하여 하나의 정렬된 배열을 만듦

 

 

 

2.3.2 알고리즘

합병 정렬의 분할 - 정복 - 결합 과정 그림 예

합병 정렬 과정의 합병 함수 알고리즘

2,3,3 성능 분석

 

합병 함수 Merge() 수행 시간

크기 n 인 배열 B 와  크기가 n 인 배열 C 를 합병하면 A[] 이면,

두 부분배열 간의 비교 횟수 : (n/2) ~ ((n/2)+(n/2)-1 = n -1 )

 

T(n)=2T(n/2)+Θ(n), T(1)=Θ(1) → O(nlogn)

-> 입력 크기 n 만큼의 추가적인 저장 장소가 필요

 

합병 정렬 MergeSort() 수행 시간 

크기 n/2인 두 번의 MergeSort()순환 호출 +한 번의 합병 Merge() 

T(n)=T(n/2)(왼쪽 데이터를 정렬하는데 걸리는 시간)

      + T(n/2) ( 오른쪽  데이터를 정렬하는데 걸리는 시간)

      +Θ(n) (왼쪽과 오른쪽이 정렬되었을때 합병하는데 걸리는 시간)

 

T(n)=2T(n/2)+Θ(n)

 

T(n)=O(nlogn)

 

합병 정렬의 최악, 최선, 평균 시간은 nlogn 이다.

( 퀵 정렬에서의 최선의 경우 와 동일 )

 

 

 

2.5 선택 문제

 

2.5.1 개념과 원리

선택 ( selection ) 문제는 n개 원소가 임의의 순서로 저장된 배열 A[0..n-1]에서 i 번쨰로 작은 원소를 찾는 문제

 

i=1 → 최솟값 

i=n/2 → 중간값  

i=n → 최댓값

 

직관 적인 방법 

오름차순으로 정렬한 후 i 번째 원소를 찾는 방법 >> O(nlogn)

최솟값 찾는 과정을 i 번 반복 (( i - 1) 번 까지는 최솟값을 찾은 후 삭제 ) >> O( in )

 

 

2.5.2 최솟값 찾기

각 데이터를 하나씩 모두 비교하는 방법

 

최솟값 찾기

n개의 데이터에 대해서 최소한 (n-1)번의 비교가 필요 → O(n)

 

2.5.3 최솟값과 최댓값 모두 찾기

최솟값 찾은 후 최댓값 찾는 방법(또는 최댓값 찾은 후 최소값 찾기)

n개의 데이터에서 최솟값을 찾는데 (n-1)번의 비교 + (n-1)개의 데이터에서 최댓값을 찾는데 (n-2)번의 비교

=> 2n-3번의 비교

 

2n-3번의 비교가 아닌 (3 / 2)n - 2 번의 비교로 수행 가능

모든 원소를 두 개씩 짝을 이루어 동시에 최솟값/최댓값과 비교

 

최솟값과 최댓값 모두 찾기

 

2.5.4 i 번째로 작은 원소 찾기 : 최악 O(n^2), 평균 O(n)

 

(1) 개념과 원리

퀵 정렬의 분할 함수 Partition()을 순환적으로 적용

 

i번째로 작은 원소 찾기 :최악 O(n2), 평균 O(n)

 

분할 피벗을 기준으로 주어진 배열을 두 부분배열로 분할, i가 피벗의 인덱스와 같으면 피벗의 값을 반환하고 종료

정복 인덱스 i가 포함된 부분배열에 대해서 선택 알고리즘을 순환적으로 적용

결합 필요없음

 

(2) 알고리즘

(3) 성능 분석

최악의 경우 = 퀵 정렬의 최악의 경우

• 분할 함수가 항상 하나의 부분배열만 생성하는 경우

• 오름차순으로 정렬된 상태에서 i = n 을 찾는 경우

→분할 함수 호출할 때 마다 피벗의 인덱스는 1씩 증가

→Partition()을 O(n)번 호출 ⇒ O(n2)

해결책 →항상 일정한 비율의 두 부분배열로 분할

→최악의 경우에도 O(n)

평균적인 경우  :  O (n)

 

 

2.5.5 i번째로 작은 원소 찾기_최악 O(n),평균 O(n)

 

(1) 개념과 원리

특정한 성질을 만족하도록 피벗을 선택

→항상 일정한 비율의 두 부분배열로 분할

 

피벗 선택 방법

1)크기 n인 배열의 원소를 5개씩 묶어 ën/5û개의 그룹을 형성

• 5의 배수가 되지 않아 그룹을 형성하지 못한 채 남는 원소는 그대로 남겨 둠

 

2)각 그룹에 대해서 중간값을 찾음

 

3) [n/5û](하한) 개의 중간값들을 대상으로 다시 중간값을 찾음

→ “중간값들의 중간값”⇒ ”피벗”

 

i 번째로 작은 원소 찾기 

 

 

 

 

 

#어려워...... # 어려워.......... #어려워 죽겟다 ㅜㅜㅜㅜㅜㅜㅜㅜ

3강 제 2 장 분학정복 알고리즘

 

3강 제 2 장 분학정복 알고리즘

 

 

 

5강 제3장 동적 프로그래밍 알고리즘

5강 제3장 동적 프로그래밍 알고리즘