![]()
0. Intro- 7-1에서 우리는 Quicksort를 직접 구현해보았다.- 이번 챕터에선 Quicksort의 시간복잡도를 한번 구해보고자 한다.- 엄밀하게 증명을 통해 구하기 보단, 직관적으로 이해하기 쉽게 알아보고자 한다. 1. Best cases- 최선의 경우 분할할 때 정확히 절반을 계속 나누는 것을 의미한다.- 깊이는 O(logn)이고, 각 순환 호출에서의 비교 연산은 O(n)이다.- 따라서 최선의 상황의 시간복잡도는 O(nlogn)이 된다. 2. Worst Cases- 최악의 경우는 정렬하고자 하는 배열이 오름차순으로 정렬되어 있거나, - 내림차순으로 정렬되어 있는 경우이다.- 깊이는 O(n)이고, 각 순환 호출에서의 비교 연산은 O(n)이므로 - 따라서 최악의 상황의 시간복잡도는 O(n^2)..
![]()
0. Intro- 이번 7 챕터에서는 quicksort, 퀵정렬에 대해서 알아보고자 한다. 1. Quicksort(퀵정렬)- quicksort(퀵정렬)은 2-3에서 배웠던 mergesort(병합정렬)과 비슷하다.- divide-and-conquer(분할정복)알고리즘을 이용한다.- 평균적으로 매우 빠른 수행 속도를 보여주기 때문에 quicksort 라고 불린다. 2. Quicksort의 알고리즘 - QuickSort의 핵심은 분할(divide)하는 과정이다. - QuickSort는 배열을 작은 부분으로 쪼개서 정렬하는 방식으로 작동하며, 다음과 같은 과정을 거친다. i) Pivot 선택- 배열에서 임의의 기준이 되는 Pivot 요소를 선택한다.- Pivot을 선택하는 방식은 크게 4가지가 존재한다. a) ..
![]()
1. Introduction- [4-5] 에선 마스터 정리에 대한 공식을 알아 봤다면, 이 공식이 어떻게 나왔는지 증명을 통해서 알아보자. 2. Proof- 1) T(n)을 시그마를 이용하여 정리한다. - 2) c - 3) c = log_b(a) 일 때, - 4) c > log_b(a) 일 때,
![]()
1. Master Theorem- 점화식으로 표현된 재귀알고리즘의 시간 복잡도를 계산할 수 있는 방법중 Master Theorem에 대해 알아보자- Master Theorem은 모든 점화식에 사용이 가능하지 않고 다음 식을 만족하는 점화식 일때만 사용이 가능하다. - a : 분할한 부분 문제의 수, b: 입력의 크기가 줄어드는 비율 , T(n/b) : 부분문제 해결 시간, f(n) : 병합에 필요한 시간 - 이렇게 되면 T(n)의 시간 복잡도를 마스터 정리를 이용하여 구하면 다음과 같다. - 이 식을 통해 알 수 있는 점은 병합에 걸리는 시간과 부분문제를 해결하는 시간 중에서 더 오래 걸리는 쪽의 영향을 더 많이 받아 시간복잡도가 정해진다는 것이다. 2.Exercise2.1) T(n) = 8 * ..
