반응형
4.1 삽입 정렬 알고리즘 성능 분석
삽입 정렬 알고리즘 성능을 분석합시다.
n 개의 원소인 배열을 정렬할 때 비교에 걸리는 수행 시간을 T'(n)이라고 합시다. 삽입 정렬의 내부 반복문에서 비교에 걸리는 시간을 S(n)이라고 하면 S(n) = n-1입니다. T'(n)은 다음과 같습니다.
T'(n) = S(2) + S(3) + ... + S(n) = 1 + 2 + 3 + ... +(n-1)
따라서 삽입 정렬의 비교에 걸리는 시간은 O(n^2)이라고 말할 수 있습니다.그리고 삽입 정렬에서 교환과 비교 횟수는 같습니다. 따라서 선택 정렬 알고리즘을 수행 시간은 O(n^2)이라고 말할 수 있습니다.
반응형
'언어 자료구조 알고리즘 > 디딤돌 정렬 알고리즘 (C언어)' 카테고리의 다른 글
5.2 퀵 정렬 알고리즘 구현 (0) | 2016.11.25 |
---|---|
5.1 퀵 정렬 알고리즘 성능 분석 (0) | 2016.11.25 |
5. 퀵 정렬(Quick Sort) 알고리즘 (0) | 2016.11.25 |
4.3 삽입 정렬 알고리즘 소스 코드 (0) | 2016.11.25 |
4.2 삽입 정렬 알고리즘 구현 (0) | 2016.11.25 |
4. 삽입 정렬(Insertion Sort) 알고리즘 (0) | 2016.11.25 |
3.3 선택 정렬 알고리즘 소스 (0) | 2016.11.24 |
3.2 선택 정렬 알고리즘 구현 (0) | 2016.11.24 |
3.1 선택 정렬 알고리즘 성능 분석 (0) | 2016.11.24 |
3. 선택 정렬(Selection Sort) 알고리즘 (0) | 2016.11.24 |