[세호/week2] 분할정복과 퀵정렬, 병합정렬

분할 정복이란

• 문제를 둘 이상의 부분으로 나누어, 부분 문제에 대한 답을 재귀 호출을 이용해 계산하는 알고리즘 디자인.
• 분할 정복을 적용하기 위해서는 ..
  1. 문제를 둘 이상의 부분 문제로 나누는 자연스러운 방법이 있어야하고
  2. 부분 분제의 답을 조합해 원래 문제의 답을 계산하는 효율적인 방법이 있어야함.        

     퀵정렬과 병합정렬

퀵정렬 : pivot 값을 정하여, pivot보다 작은 값은 왼쪽으로, 큰 값은 오른쪽으로(오름차순 정렬인 경우) 이동시키며 정렬하는 방법.

1. Worst Case : 이미 데이터가 정렬되어 있는 경우  : T(n) = T(n-1) + T(1) + n-1    -> Time complexity = O(n2)

2. Best Case : pivot이 항상 데이터의 중간값인 경우 (항상 절반으로 나눔)  : T(n) = T(n/2) + T(n/2) + n-1  Time complexity =

3. O(nlogn) Average Case =    

   병합정렬 : 데이터를 절반씩 나누어, 1개까지 나누고 다시 정렬하면서 합치는 정렬 방법.

• 항상 시간 복잡도가 O(nlogn)    

  귀류법

  원하는 바와 반대되는 상황을 가정하고 논리를 전개해서 결론이 잘못되었음을 찾아내는 증명 기법.        

  수학적 귀납법과 반복문 불변식

• 수학적 귀납법 : 단계로 나눌 수 있는 문제에 대해서, 첫 단계가 만족하면 그 이후 모든 단계에서도 만족함을 보이는 방법.
• 과정
  1. 첫번째 단계(초기조건)에서 어떤 명제가 성립함을 보인다.
  2. 임의의 k번째 단계에서 명제가 성립함을 가정한다.
  3. 위에서 가정한 조건을 이용하여 k+1번째 단계도 성립함을 보인다.
  4. 따라서 모든 단계에서 성립한다.
• 반복문 불변식 : 수학에서 귀납법을 이용하는 것과 유사하게, 알고리즘의 반복문에서 그 알고리즘이 제대로 동작하는지를 증명하기 위한 식.
• 반복문의 정당성을 증명하는 방법 :
  1. 반복문이 처음 시작될 때 불변식이 만족함을 보인다.
  2. 반복문이 반복되는 도중에도 조건이 유지됨을 보인다.

• 2019 14