2장 Divide and conquer

chap2. Divide and conquer

• problem을 subproblem으로 나누어 따로 풀고 합치는 방식. = top→ down approach

3-basic step

1. Divide
2. conquer(solve subP)
3. if necessary combine

binary search = sorted input

= T(n) = T(n/2) -> time complexity = logn

every time complexity

recurrence relation Master Theorem

재귀방식에 적용 가능한 time complexity 구하는 법

• 재귀함수가 몇번 불렸는지(a) 몇 개로 나누어 푸는지(b)를 구하고, 함수 T(n)의 재귀 외의 나머지 함수에 대해서 n^d 형태로 만들어 d를 구한다. 그 후 위 공식에 대입.

merge sort - every time complexity = not sorted input

• mergesort 함수와 merge함수가 있고, 배열을 둘로 나누어 mergesort를 한 후 두 배열을 merge해주는 형태.
• basic operation= n>1 을 만족할 때까지 Mergesort가 재귀적으로 불리는 operation
• time complexity = T(n) = 2T(n/2)+f(n)
• f(n) = division(n) + merge(n) = 1 +n-1 =n
• a=2 b=2 , d=1(f(n)= n 이 n의 1승이라 1 임.) → nlogn
• merging 이 linear time (n번)안에 해결되고, mergesort로 분할하는 division과정이 logn만큼 걸려서 저런 complexity가 나옴.
• 입력배열의 크기만큼 메모리를 추가 사용한다는 단점이 있긴 함.

quicksort = not sorted input, not every case

• 선택된 값 pivot 값을 기준으로 왼쪽과 오른쪽으로 divide 한다.
• spliting position인 pivot 값에 따라 complexity가 달라진다.
• partition을 정하는 함수로 배열을 찢고 찢어진 두 배열에 대해 재귀적으로 quicksort 함수반복 실행하는 형태

partition function1. lomutopartitioning

partition function2. Hoare’s partitioning

• basic operation = partition부분의 배열값과 pivot값의 비교연산
• best case = balanced partition = T(n) = 2T(n/2) +n for n>1 T(1)=0 -> nlogn
• worst case = 이미 정렬된 것 T(n)= n+1 +n+n-1+..+3 = n^2
• average case = nlogn
• 즉 quick sort가 효율이 좋으려면 적당한 pivot값 선택이 필요하다.
• 이를 해결하기 위해 처음 중간 끝의 값 중 중앙값을 pivot으로 선택하거나 random선택하는 방법이 존재한다.
• 문제점 = 둘 다 추가 저장장소가 필요.

multiplication of Tow large integer

time complexity = M(n) = 3M(n/2), for n>1 , M(1)=1 n^(log_2(3) ~= 1.585)

multiplication two large matrix

time complexity 계산