PS/알고리즘
정렬-2
더 빠르게 정렬할 수는 없을까? 기존의 정렬의 시간 복잡도는 O(n^2) 걸리지만 오늘 배울 합병 정렬과 퀵 정렬은 시간 복잡도가 O(n log n)이 걸리게 된다. 두 정렬은 모두 재귀를 사용하게 된다. 재귀 함수 디자인의 과정 1. 작성하려는 함수의 역할을 말로 명확하게 정의한다. 2. 함수가 기저 조건에서 제대로 동작하게 작성한다. 3. 함수가 제대로 동작한다고 가정하고 함수를 완성한다. 4. 함수를 완성한 후, 기저 조건으로 수렴함을 보인다. 합병 정렬 배열을 절반으로 나누어 각각을 정렬한 후, 합친다. T(n) = n개의 숫자를 합병 정렬할 때의 시간 복잡도 1. 왼쪽 합병 정렬 = T(n/2) 2. 오른쪽 합병 정렬. = T(n/2) 3. 합친다. = O(n) 점화식 = T(n) =2*T(n/..
