정렬 안정성 과 알고리즘 시간 복잡도 빅오(Big - Oh)

안녕하세요.

정렬과 탐색 알고리즘 관련 글을 작성 중 간단하게 안정성과 빅오 표기법에 대한 글을 작성하고

첨부해 놓으면 좋을 거 같아서 따로 작성하게 되었습니다.

정렬 알고리즘 구현에 있어서 고려되는 사항인 안정성과

알고리즘에서 중요한 빅오(시간 복잡도)를 알아보도록 하겠습니다.

 

1. 정렬에서 안정성(Stability)이란?

 

정렬되지 않은 데이터들 중에서 같은 값 이 있다고 했을때 그 값들 순서의 보장 유무를 뜻합니다.

안전성이 없다는 것은 1(A), 1(B), 1(C) 가 있다고 했을때

1끼리는 정렬이 되지만 정렬 전 1끼리의 순서 연속성은 보장할 수 없다라는 것을 뜻합니다.

1(B) 가 먼저 나올지 1(C) 가 나올지 1(A) 가 먼저 나올지 예측할 수 없습니다.

반대로 안전성이 있다는 것은 1(A), 1(B), 1(C) 의 순서가 보장 된다는 것을 뜻합니다

정렬 전

1(A) 4 2 1(B) 5 1(C) 3 

정렬 후

1(A) 1(B) 1(C) 2 3 4 5 = 안전성이 있다.

1(B) 1(A) 1(C) 2 3 4 5 = 안전성이 없다.

 

2. 시간 복잡도 빅오(Big - Oh / Big - O) 표기법 

 

입력되는 데이터 수 N 에 대하여 시간(연산 횟수) 증가를 표현한 표기법을 정리 해보았습니다.

 

O(1) - 상수형 빅오

입력 데이터 수에 상관 없이 일정 시간 (연산 홧수)를 가지는 알고리즘 입니다.

1회 이든 5회이든 실행횟수와 상관없이 상수임을 뜻하기 위해 1 을 사용합니다.

 

O(log n) - 로그형 빅오

입력 데이터 수 증가에 비해서 시간 (연산 횟수) 가 적은 알고리즘을 뜻합니다.

성능 좋은 알고리즘은 대부분 여기에 속합니다.

 

O(n) - 선형 빅오

입력 데이터 수 증가에 비례해서 시간 (연산횟수)가 증가하는 알고리즘을 뜻합니다.

데이터 수가 2배로 늘어나면 실행시간도 2배 만큼 증가합니다.

 

O(n log n) - 선형 로그형 빅오

입력 데이터 수 증가에 비해서 시간 (연산횟수)가 조금 더 증가하는 알고리즘을 뜻합니다.

데이터 수가 2배로 늘어나면 실행시간은 2배 보다 조금 더 증가합니다.

성능 좋은 정렬 알고리즘의 실행시간이 여기에 속합니다.

 

O(n²)

입력 데이터 수의 제곱에 해당하는 시간 (연산횟수)를 갖는 알고리즘을 뜻합니다.

데이터 수가 2배로 늘어나면 실행시간은 4배 증가합니다.

보통 이중 루프 내에서 입력 자료를 처리 하는 경우에 발생합니다.

많은 데이터를 입력 할 경우 사용이 부적절한 알고리즘 입니다.

 

O(n³)

입력 데이터 수의 3제곱에 해당하는 시간 (연산횟수)를 갖는 알고리즘을 뜻합니다.

데이터 수가 2배로 늘어나면 실행시간은 8배 증가합니다.

보통 삼중 루프 내에서 입력 자료를 처리 하는 경우에 발생합니다.

O(n²) 와 마찬가지로 많은 데이터를 입력 할 경우 사용이 부적절한 알고리즘 입니다.

 

O(2ⁿ) - 지수형 빅오

입력 데이터 수 증가에 비해서 시간 (연산횟수)가 급격히 증가하는 알고리즘을 뜻합니다.

데이터 수가 2배로 늘어나면 실행시간은 제곱으로 증가합니다.

사용 하기에는 문제가 많은 알고리즘 입니다.

 

정렬

버블 정렬(Bubble Sort) - 안정성 O, O(N²)

선택 정렬(Select Sort) - 안정성 X, O(N²)

삽입 정렬(Insert Sort) - 안정성 O, O(N²)

쉘 정렬(Shell Sort) - 안정성 X, O(n^1.5)

병합 정렬(Merge Sort) - 안정성 O, O(N log N)

퀵 정렬(Quick Sort) - 안정성 X, O(N log N)