빅 오 표기법은 주어진 상황에 적합한 알고리즘을 결정하는데 도움을 주는 도구이다.
하지만 유일한! 도구는 아니라는 것.
한 알고리즘이 다른 알고리즘보다 더 빠른 경우에도 같은 방식으로 표기하곤 하는데,
이 케이스의 예로는 버블 정렬과 선택 정렬이 있다.
여기에서는 선택 정렬에 대해 정리한다.
선택 정렬 (Selection Sort)
수행 단계
선택 정렬은 다음과 같은 단계를 따른다.
- 배열의 각 셀을 끝까지 이동하며 어떤 값이 최솟값인지를 확인.
그 값의 인덱스를 변수에 저장한다. - 배열 끝까지 이동하여 최솟값을 확인하고 나면, 시작한 인덱스의 값과 최솟값을 교환한다.
(만약 시작한 인덱스의 값이 최솟값인 경우, 즉 그대로인 경우 교환 없이, 다음 인덱스로 이동하여 위의 단계를 수행한다.)
여기서 마지막에 위치한 값은 따로 단계를 수행하지 않아도 정렬되어 있으므로 실행하지 않는다. (배열의 길이-1 만큼 정렬을 위한 단계 수행)
효율성
선택 정렬은 비교와 교환, 두 종류의 단계를 포함하고 있다.
5개의 원소를 포함하는 배열의 경우, 4 + 3 + 2 + 1 번의 비교를 수행해야 하며,
이는 (N-1) + (N-2) + (N-3) + (N-4) + ... + 1 번의 비교이다.
교환의 경우, 한 번의 패스스루 당 1번의 교환이 일어나게 된다.
이는 계산해보면 대략적으로 N^2 /2 의 단계가 필요하다고 계산되는데,
중요한 건
빅 오 표기법은 상수를 무시한다.
는 조건에 따라, 선택 정렬의 빅 오 표기법은 O(N^2) 이다.
이는 정렬이 될 때까지 바로 옆 인접한 인덱스 값과 값을 비교하여 교환이 이루어지는,
더 많은 시간이 소요되는 버블 정렬과 같은 표기 방식이다.
즉 두 알고리즘 모두 빅 오로는 O(N^2)이지만,
선택 정렬은 버블 정렬보다 두 배 정도 빠르다는 점이다.
빅 오 카테고리
빅 오 표기법은 일반적인 카테고리의 알고리즘 속도만 고려한다는 점이다.
예를 들어, 1층짜리 2층짜리 3층짜리 단독 주택과 100층짜리 고층 빌딩과 비교할 경우,
단독 주택이 얼마나 높은 층수이던 100층짜리 고층 건물과는 비교가 되지 않기 때문에
그냥 집 / 고층 빌딩 이라고 부르는 편이 낫다는 것이다.이처럼 빅오 표기법도 일반적인 카테고리로만 분류해도 현저한 차이를 나타내기 때문에,
N, 4N, 100N 과 N^2는 비교가 되지 않으므로 그냥 O(N) / O(N^2)으로 표기하는 것이다.
그렇기 때문에 빅 오 표기는 서로 다른 카테고리에 속하는 알고리즘을 대조할 때는 완벽한 비교 도구가 될 수 있지만, 같은 카테고리에 속하는 알고리즘이라면 어떤 알고리즘이 더 빠를지는 보다 분석해보아야 한다.
이는 알고리즘 복습을 위해 "누구나 자료구조와 알고리즘" 책을 읽고 배운 점을 기록한 내용입니다.
참고하면 좋을 링크 : https://bit.ly/3ZN5bGH
