performance of quicksort

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)..
23학번이수현
'performance of quicksort' 태그의 글 목록