반응형
[C언어 알고리즘] 2.3.1 버블 정렬 알고리즘 성능 분석
버블 정렬 알고리즘 성능을 분석합시다.
버블 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)
반복(i:=n; i>1 ; i:= i-1)
반복(j:=1; j<i ; j:=j+1)
조건(compare(base[j-1], base[j]) > 0)
교환(base[j-1],base[j])
n 개의 원소인 배열을 정렬할 때 비교에 걸리는 수행 시간을 T'(n)이라고 합시다. 버블 정렬의 내부 반복문에서 비교에 걸리는 시간을 S(n)이라고 하면 S(n)=n-1입니다. 따라서 T'(n)은 다음과 같습니다.
T'(n) = S(n) + S(n-1) + ... + S(2) = (n-1) + (n-2) + (n-3) + ... + 3 + 2 + 1
따라서 버블 정렬의 비교에 걸리는 시간은 O(n^2)이라고 말할 수 있습니다.
n 개의 원소인 배열을 정렬할 때 교환에 걸리는 수행 시간을 T"(n)이라고 합시다. 버블 정렬의 내부 반복문에서 교환하는 시간을 R(n)이라고 하면 최악일 때 R(n)=n-1입니다. 그리고 T"(n)은 다음과 같습니다.
T"(n) = R(n) + R(n-1) + ... + R(2) = (n-1) + (n-2) + (n-3) + ... + 3 + 2 + 1
마찬가지로 버블 정렬의 교환에 걸리는 시간은 O(n^2)이라고 말할 수 있습니다. 따라서 버블 정렬 알고리즘을 수행 시간은 O(n^2)이라고 말할 수 있습니다.
반응형
'언어 자료구조 알고리즘 > 디딤돌 알고리즘 (C언어)' 카테고리의 다른 글
[C언어 알고리즘] 2.4.2 선택 정렬 알고리즘 구현 (0) | 2016.11.29 |
---|---|
[C언어 알고리즘] 2.4.1 선택 정렬 알고리즘 성능 분석 (0) | 2016.11.29 |
[C언어 알고리즘] 2.4 선택 정렬(Selection Sort) 알고리즘 (0) | 2016.11.29 |
[C언어 알고리즘] 2.3.3 버블 정렬 알고리즘 소스 코드 (0) | 2016.11.29 |
[C언어 알고리즘] 2.3.2 버블 정렬 알고리즘 구현 (0) | 2016.11.29 |
[C언어 알고리즘] 2.3 버블 정렬(Bubble Sort) 알고리즘 (0) | 2016.11.29 |
[C언어 알고리즘] 2.2.3 순차 정렬 알고리즘 소스 코드 (0) | 2016.11.29 |
[C언어 알고리즘] 2.2.2 순차 정렬 알고리즘 구현 (0) | 2016.11.29 |
[C언어 알고리즘] 2.2.1 순차 정렬 알고리즘 성능 분석 (0) | 2016.11.29 |
[C언어 알고리즘] 2.2 순차 정렬(Sequential Sort) 알고리즘 (0) | 2016.11.29 |