chapter 2. divide-and-conquer

설계 전략

Divide: 해결하기 쉽도록 문제를 여러 개의 작은 부분으로 나눈다.
Conquer: 나눈 작은 문제를 각각 해결한다.
Combine: 해결된 해답을 모은다.
=> 하향식(top-down)

이분 검색: 재귀적 방식

분할: 배열을 반으로 나누어서 중앙에 위치한 값과 x를 비교해서 두 배열 중 하나를 선택
정복: 선택된 반쪽 배열에서 x를 찾는다.

시간복잡도

경우 1: 검색하게 될 반쪽 배열의 크기가 항상 정확하게 n/2이 되는 경우

경우2: 일반적인 경우 - 반쪽 배열의 크기는 n/2의 같거나 작은 실수

합병정렬

합병 알고리즘 시간복잡도 분석(최악)
W(h,m) = h+m-1 (예 U: 4,5,6,7   V: 1,2,3,8)

합병정렬 알고리즘 시간복잡도 분석(최악)
W(h,m) = W(h) + W(m) + h + m - 1 (h와 m 정렬하고 합병하는데 걸리는 시간)
재현식: W(n) = 2W(n/2) + n - 1 (정수 n을 2**k라고 가정)

master theorem-2를 사용하면 W(n) = n*lg(n)

공간복잡도 분석

n+n/2+n/4+... = 2n

공간복잡도가 향상된 알고리즘

Quicksort

분할알고리즘(partition) 모든 경우 시간복잡도 분석

T(n) = n - 1 ( 첫 번째 항목 제외 모든 항목과 비교 )

quicksort 최악의 경우 시간복잡도 분석 

재현식: T(n) = T(n - 1) + n - 1 ( 입력이 비내림차순으로 정렬이 되어 있다면 두 덩어리로 분리되지 않음 )
T(n) = n*(n-1)/2

행렬 곱셈

시간복잡도 분석

• 단위 연산이 가장 안쪽 곱셈 연산, T(n) = n*n*n
• 단위 연산이 가장 안쪽 덧셈 연산, T(n) = (n-1)*n*n (곱셈을 n번할때 덧셈은 n-1번함)

쉬트라쎈의 방법

시간복잡도 분석: 7번의 곱셈 + 18번의 덧셈/뺄셈 , 2x2 행렬 곱셈에서 8번의 곱셈과 4번의 덧셈이 쓰였는데 전혀 좋아지지 않은 것 같다. 그러나 행렬의 크기가 커지면 쉬트라쎈의 방법이 효율적이다.

행렬 곱셈 시간복잡도 분석

• 단순한 방법의 시간복잡도
  재현식 : T(n) = 8T(n/2)
• 쉬트라센 방법의 시간복잡도
  단위연산이 곱셈일 때 재현식 : T(n) = 7T(n/2)
  단위연산이 덧셈/뺄셈일 때 재현식 : T(n) = 7T(n/2) + 18(n/2)**2

큰 정수 계산법

prod 최악의 경우 시간복잡도 분석

• W(n) = 4W(n/2) + cn (n > s 이고, n이 2의  거듭제곱인 경우)
• W(s) = 0 (s=threshold보다 작거나 같은 문제크기, W(s)의 단위연산 횟수는 0)

개선된 방법

• 이전 방법에서는 4회의 곱셈 필요
• 개선 방법: r 계산 추가
  • r = (x+y) * (w+z) = xw + (xz + yw) + yz
• 덧셈/뺄셈의 횟수는 증가하지만 곱셈은 3회 필요

• 최악의 경우 시간복잡도 분석
  • 3W(n/2) + cn <= W(n) <= 3W(n/2 + 1) + cn

도사 정리

재현식: T(n) = a * T(n/b) + f(n) (a,b > 1, f(n)을 어떤 함수라 하자)

• 점근적인 한계점