한국어
메뉴

자료 구조와 알고리즘

퀵 정렬의 시간 복잡도가 O(n²)이 되는 전형적인 경우는?

  1. A데이터가 뒤죽박죽으로 늘어서 있고, 피벗(기준값)을 무작위로 고르는 경우
  2. B데이터의 개수가 2의 거듭제곱인 경우
  3. C이미 정렬된 데이터에서 항상 맨 앞의 원소를 피벗으로 하는 경우
정답과 해설 보기

정답: C. 이미 정렬된 데이터에서 항상 맨 앞의 원소를 피벗으로 하는 경우

퀵 정렬은 피벗보다 작은 원소와 큰 원소로 나누고, 각각을 다시 나누어 갑니다. 정렬된 데이터에서 항상 맨 앞을 피벗으로 하면 매번 피벗이 최솟값이 되어 분할이 '0개와 나머지 전부'로 치우치므로, 비교는 n(n−1)/2회(n = 100이면 4,950회)가 됩니다. 피벗을 무작위로 고르거나 세 값의 중앙값으로 하면, 치우친 분할이 계속될 가능성은 매우 작아집니다. 데이터의 개수는 시간 복잡도와 관계가 없습니다.

이 분야 연습하기 분야로 돌아가기

자료 구조와 알고리즘의 다른 문제

  1. 병합 정렬에서 오름차순으로 정렬된 두 열 1, 4, 7, 9와 2, 3, 8, 10을, 맨 앞끼리 비교하여 작은 쪽을 출력하는 것을 반복하여 하나의 열로 합친다(병합한다). 한쪽 열이 비면 나머지는 비교하지 않고 그대로 출력한다. 비교 횟수는 몇 회인가?
  2. 이진 힙을, 루트를 a[0]으로 하는 배열 a[0], a[1], a[2], …에 위쪽 단부터 차례로 왼쪽부터 채워 저장한다. a[4]의 자식과 부모로 올바른 것은?
  3. 부모의 값이 자식의 값 이상이 되는 최대 힙을, 루트를 a[0]으로 하는 배열로 나타내고 있다. 힙 50, 30, 40, 10, 20, 35에 45를 추가한다. 맨 끝에 놓은 뒤 부모보다 큰 동안은 부모와 교환하는 조작을 수행한 후의 배열은?
  4. 이진 탐색 트리를 중위 순회(왼쪽 서브트리, 그 노드, 오른쪽 서브트리 순으로 방문한다)로 따라갔을 때, 방문한 노드의 값은 어떻게 늘어서는가? 값은 모두 서로 다르다고 한다.
  5. 빈 이진 탐색 트리에 50, 30, 70, 20, 40, 60, 80의 순서로 값을 삽입했다. 이 트리를 후위 순회(왼쪽 서브트리, 오른쪽 서브트리, 그 노드 순으로 방문한다)로 따라갔을 때의 순서는?