(A+, 만점취득) 방송통신대학교 컴퓨터과학과 알고리즘

소개글

"방송통신대학교 컴퓨터과학과 알고리즘"에 대한 내용입니다.

목차

1. 문제1
2. 문제2
3. 문제3
4. 문제4
5. 문제5

본문내용

알고리즘의 성능을 평가할 때 시간 복잡도 라는 개념을 사용하는데 시간 복잡도란 점근 표기법을 사용하여서 표기하는 것으로 점근 표기법은 함수의 입력이 증가함에 따라서 그 출력 값이 얼마나 증가하는지를 표현한 것이다. 퀵 정렬이란 피벗(pivot)을 기준으로 주어진 배열을 두 부분 배열로 분할하는 것으로(왼쪽 부분 배열의 모든 값 < 피벗 < 오른쪽 부분 배열의 모든 값) 두 부분 배열에 대해서 각각 퀵 정렬을 순환적으로 적용함으로 정렬시키는 알고리즘이다. 퀵 정렬에서 피벗이 제자리를 잡도록 해주면서 두 부분 배열로 분할해주는 함수가 바로 분할 함수 Partition( ) 이다. 그러므로 분할 함수 Partition( )이 어떻게 동작하는지 이해하는 것이 퀵 정렬에서 핵심이 되는 부분이다. 분할 함수 Partition( )의 수행 시간의 시간 복잡도는 Θ(n) 또는 O(n) 이다. 분할 함수란 어떠한 배열이 주어졌을 때 피벗을 기준으로 피벗보다 작은 값들은 왼쪽 부분 배열로, 피벗보다 큰 값들은 오른쪽 부분배열로 나눠주는 함수로 데이터가 n 개 주어졌을 때 피벗과 비교한 횟수는 데이터 개수 n 에 비례하게 되기 때문이다. 즉 이는 데이터 개수에 선형적으로 비례하는 시간을 갖는 것으로 데이터가 10 개, 100 개이면 그것에 대해 선형적으로 비례하여서 증가하는 시간을 갖는 갖게 됨으로 분할 함수 Partition( )의 수행 시간의 시간 복잡도는 Θ(n) 또는 O(n) 이 된다.
퀵 정렬이란 피벗(pivot) 원소를 정하고(기본적으로 배열의 첫 번째 원소를 피벗 원소로 정한다) 정해진 피벗 원소를 기준으로, 피벗보다 작은 값들은 왼쪽 부분 배열에 배치하고, 피벗보다 큰 값들은 오른쪽 부분 배열에 배치하는 것으로 즉, ‘왼쪽 부분 배열의 값 < 피벗 < 오른쪽 부분 배열의 값’ 과 같은 형태로 피벗이 제자리를 잡도록 정렬해주는 것이다. 왼쪽 부분 배열과 오른쪽 부분 배열에 대해서 퀵 정렬을 순환적으로 적용함으로 최종적으로 정렬된 값을 구할 수 있다. 퀵 정렬에서 분할되는 두 부분 배열의 크기는 일정하지 않으며, 결합단계가 필요하지 않다.

참고 자료

없음