분할정복 알고리즘 2

- 합병 정렬, 선택 문제

 

- 합병 정렬

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

    정렬된 두 부분배열을 합명 -> 하나의 정렬된 배열을 만듦

  - 분할, 정복, 결합

  - 합병 정렬은 합병이 중요함 ( 퀵정렬은 분할이 중요 )

  - A, B 원소를 하나씩 비교, 남은 하나는 그냥 추가

     - 합병 함수 Merge() 수행 시간 ->최악의 경우 세타(n) 선형적으로.

   

     - 입력 데이터 개수만큼의 저장 장소가 추가로 필요 (제자리 정렬 알고리즘이 아님)

  - 합병 정렬 MergeSort() 수행 시간

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

     - T(n) = 2T(n/2) + theta(n)

        -> T(n) = O(nlon)

  - 비순환전 합병 정렬 -> 합병만 반복적으로 함

 

- 선택 문제?

  - n 개의 원소가 임의의 순서로 저장된 배열 A에서 i 번째로 작은 원소를 찾는 문제

     - i = 1 : 최솟값, i = n/2 : 중간값, i =n : 최댓값

  - 직관적인 방법

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

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

  - 최솟값 찾기

    - 각 데이터 비교 -> O(n)

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

    - n개에서 최솟값 찾는데 n-1번의 비교, n-1개에서 최댓값 찾는데 n-2 비교 -> 2n-3비교

    - 3/2*n - 2 번의 비교로도 수행 가능

      - 모든 원소를 두 개씩 짝을 이루어 비교

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

    - 개념과 원리

      - 퀵 정렬의 분할 함수를 순환적으로 적용

      - 분할 ( 피벗 기준으로 두 부분배열로 분할, i가 포함된 부분 배열에 대해 정복, 합병 필요 x

    - 성능 분석

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

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

        - 해결책 -> 항상 일정한 비율의 두 부분배열로 분할 -> 최악의 경우에도 O(n)

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

    - 특정한 성질을 만족하도록 피벗을 선택 ( 항상 일정한 비율의 두 부분배열로 분할 )

    - 피벗 선택 방법

      - 크기 n인 배열의 원소를 5개씩 묶어 n/5개의 그룹 형성, 5의 배수가 안되면 그대로 나둠

      - 각 그룹의 중간값의 중간값을 피벗으로

    - 분할 할 때마다 탐색 대상에서 제외되는 원소의 개수가 있음

 

 

① 합병 정렬 → 크기가 n인 문제를 크기가 n/2인 2개의 작은 문제로 분할

 

② 이진 탐색 → 크기가 n인 문제를 크기가 n/2인 2개의 작은 문제로 분할하고, 그 중 하나의 작은 문제는 처리 대상에서 제외

 

③ 선택 문제 → 크기가 n인 문제를 크기가 감소하지만 일정하지 않은 2개의 작은 문제로 분할하고, 그 중 하나의 작은 문제는 처리 대상에서 제외

 

④ 퀵 정렬 → 크기가 n인 문제를 크기가 감소하지만 일정하지 않은 2개의 작은 문제로 분할

 

① 합병 정렬 → 크기가 n인 문제를 크기가 n/2인 2개의 작은 문제로 분할

 

② 이진 탐색 → 크기가 n인 문제를 크기가 n/2인 2개의 작은 문제로 분할하고, 그 중 하나의 작은 문제는 처리 대상에서 제외크기가 n인 두 부분배열을 합병하면 결과 배열에는 n+n=2n개의 원소가 저장되는데, 이 과정에서 최악의 경우 n+n-1=2n-1회의 비교가 필요하며, 따라서 합병하는 데 걸리는 시간은 입력 크기 n에 비례하는 O(n)이 된다.

 

③ 선택 문제 → 크기가 n인 문제를 크기가 감소하지만 일정하지 않은 2개의 작은 문제로 분할하고, 그 중 하나의 작은 문제는 처리 대상에서 제외

 

④ 퀵 정렬 → 크기가 n인 문제를 크기가 감소하지만 일정하지 않은 2개의 작은 문제로 분할

 

 

크기가 n인 두 부분배열을 합병하면 결과 배열에는 n+n=2n개의 원소가 저장되는데, 이 과정에서 최악의 경우 n+n-1=2n-1회의 비교가 필요하며, 따라서 합병하는 데 걸리는 시간은 입력 크기 n에 비례하는 O(n)이 된다.

크기가 n인 두 부분배열을 합병하면 결과 배열에는 n+n=2n개의 원소가 저장되는데, 이 과정에서 최악의 경우 n+n-1=2n-1회의 비교가 필요하며, 따라서 합병하는 데 걸리는 시간은 입력 크기 n에 비례하는 O(n)이 된다.

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

입력 크기 n인 합병 정렬의 수행 시간 T(n)은 크기 n/2의 왼쪽 부분배열을 정렬하는데 걸리는 시간 T(n/2)과 크기 n/2의 오른쪽 부분배열을 정렬하는 데 걸리는 시간 T(n/2), 그리고 두 부분배열을 합병하는 데 걸리는 시간 O(n)의 합으로 표현된다. 

정리하기

1.합병 정렬
- 주어진 배열을 동일한 크기의 두 개의 부분배열로 분할하고, 각각의 부분배열을 순환적으로 정렬한 후, 정렬된 두 부분배열을 합병하여 하나의 정렬된 배열을 만드는 정렬 방식
- 합병 함수 Merge() : 정렬된 두 부분배열을 합병하여 하나의 정렬된 배열을 만드는 함수 → Θ(n)
- 성능 : T(n)=2T(n/2)+Θ(n), T(1)=Θ(1) → O(nlogn)
- 입력 크기 n 만큼의 추가적인 저장 장소가 필요

 

2.선택 문제
- 임의의 순서로 주어진 n개의 원소에 i번째로 작은 원소를 찾는 문제 → i=1이면 최솟값, i=n/2이면 중간값, i=n이면 최댓값을 찾는 문제가 됨
- 최소값(또는 최댓값) 찾기 : n개의 숫자에 대해서 최솟값/최댓값을 찾기 위해서는 최소한 (n-1)번의 비교가 필요 → O(n)
- 최소값과 최댓값 모두 찾기 : 모든 원소를 두 개씩 짝을 이루어 큰 값과 작은 값을 찾고, 큰 값과 최댓값 그리고 작은 값과 최솟값의 비교를 수행 → (3n)/2-2번의 비교
- 퀵 정렬의 분할 함수를 이용한 선택 문제 → 최악 O(n^2), 평균 O(n)
- 중간값들의 중간값을 이용한 선택 문제 → 크기 n인 배열의 원소를 5개씩 묶어 ⌊n/5⌋개의 그룹을 형성한 후, 각 그룹에 대해서 중간값을 찾고, 다시 각 그룹의 중간값들을 대상으로 다시 중간값을 취해서 사용 → 한 번 분할할 때마다 3×⌈⌊n/5⌋/2⌉개의 원소가 탐색 대상에서 제외 → 최악 O(n), 평균 O(n)

 

정리하기

1.합병 정렬
- 주어진 배열을 동일한 크기의 두 개의 부분배열로 분할하고, 각각의 부분배열을 순환적으로 정렬한 후, 정렬된 두 부분배열을 합병하여 하나의 정렬된 배열을 만드는 정렬 방식
- 합병 함수 Merge() : 정렬된 두 부분배열을 합병하여 하나의 정렬된 배열을 만드는 함수 → Θ(n)
- 성능 : T(n)=2T(n/2)+Θ(n), T(1)=Θ(1) → O(nlogn)
- 입력 크기 n 만큼의 추가적인 저장 장소가 필요

 

2.선택 문제
- 임의의 순서로 주어진 n개의 원소에 i번째로 작은 원소를 찾는 문제 → i=1이면 최솟값, i=n/2이면 중간값, i=n이면 최댓값을 찾는 문제가 됨
- 최소값(또는 최댓값) 찾기 : n개의 숫자에 대해서 최솟값/최댓값을 찾기 위해서는 최소한 (n-1)번의 비교가 필요 → O(n)
- 최소값과 최댓값 모두 찾기 : 모든 원소를 두 개씩 짝을 이루어 큰 값과 작은 값을 찾고, 큰 값과 최댓값 그리고 작은 값과 최솟값의 비교를 수행 → (3n)/2-2번의 비교
- 퀵 정렬의 분할 함수를 이용한 선택 문제 → 최악 O(n^2), 평균 O(n)
- 중간값들의 중간값을 이용한 선택 문제 → 크기 n인 배열의 원소를 5개씩 묶어 ⌊n/5⌋개의 그룹을 형성한 후, 각 그룹에 대해서 중간값을 찾고, 다시 각 그룹의 중간값들을 대상으로 다시 중간값을 취해서 사용 → 한 번 분할할 때마다 3×⌈⌊n/5⌋/2⌉개의 원소가 탐색 대상에서 제외 → 최악 O(n), 평균 O(n)