빅 오 표기법 : 알고리즘 성능을 표기하는 방법

들어가며

 이번 글은 알고리즘 연산 수를 수치로 나타내는 방법인 빅 오 표기법과 대표적인 시간 복잡도를 알아봅니다.

 이 글은 책 리얼 월드 알고리즘을 바탕으로 정리했습니다.

빅 오 표기법 : 알고리즘 성능을 표기하는 방법

알고리즘의 성능을 고려하는 방법

알고리즘의 성능은 입력에서 출력까지 수행하는 연산 수에 따라 결정됩니다. 이러한 연산 수를 알고리즘의 실행 시간이라고도 말합니다.

우리는 이 알고리즘 실행 시간을 이야기할 때, 일반적으로 입력 데이터 n이 무한히 클 때를 염두 합니다. 이렇게 입력 데이터가 무한히 증가할 때, 알고리즘의 연산 수(성능)를 점근적 실행 시간(asymptotic running time)이라고 합니다. 알고리즘의 점근적 실행 시간은 몇가지 표기법을 사용하여 표현하는 데, 이 중 하나가 이번 글에서 알아볼 빅 오 표기법(Big O notation) 입니다.

컴퓨터의 알고리즘은 무한한 입력을 고려합니다.
이 때, 알고리즘의 성능을 점근적 실행 시간이라고 합니다.

빅 오 표기법이란?

빅 오 표기법은 점근적 실행 시간에 대하여 상한 값을 고려한 표기법입니다. 빅 오 표기법에 관한 정확한 정의는 다음과 같습니다.

모든 n ≧ n_0 에 대해 0 ≦ f(n) ≦ cg(n)인 양의 상수 c와 n_0가 있으면 O(f(n)) = g(n)이라고 한다.

즉, 빅 오 표기법은 실제 알고리즘 실행 시간(*f(n)*)을 상한 값(g(n))으로 단순히 표현하는 것입니다. 예를 들어, 다음과 같은 실행 시간을 갖는 *f(n)*이 있는 경우, 빅 오 표기법으로 표기하는 방법은 다음과 같습니다.

1. 실제 실행 시간을 나타내는 *f(n)*

   $$f(n) = 3n^3+5n^2+2n+1000$$

2. *0 ≦ f(n) ≦ cg(n)* 를 만족하는 *g(n)*을 찾는다.

   $$0 ≦ f(n) ≦ cn^3 (c≧4)$$

3. *O(f(n)) = g(n)*

   $$O(f(n)) = g(n) = n^3$$

대표적인 시간 복잡도

 알고리즘의 실행 시간을 계산 복잡도 혹은 시간 복잡도라고 합니다. 알고리즘의 실행 시간을 연구할 때는 단순화된 몇가지 함수 중 하나가 됩니다.

상수 시간 복잡도

$$O(1)$$

• 가장 빠른 실행 시간
• 대표적으로 배열 중 특정 인덱스의 값에 접근하는 경우

로그 시간 복잡도

$$O(log(n))$$

• 문제를 분할하여 푸는 알고리즘
• 탐색 알고리즘과 관련

선형 시간 복잡도

$$O(n)$$

• 전체 입력 데이터를 스캔해야 하는 알고리즘

로그 선형 시간 복잡도

$$O(nlog(n))$$

• 문제를 분할하고 각 부분에 선형 시간 알고리즘을 적용하는 경우
• 좋은 정렬 알고리즘은 로그 선형 시간 복잡도를 가짐

2차 시간 복잡도 (다항 시간 복잡도)

$$O(n^2)$$

• 많은 알고리즘이 다항 시간 복잡도에 해당
• 일부 비효율적인 정렬 방법은 2차 시간에 실행
• n 자릿수인 두 수를 곱하는 보편적인 방법과 동일한 작동

지수 시간 복잡도

$$O(c^n)$$

• 거듭 제곱 시간

팩토리얼 시간 복잡도

$$O(n!)$$

• 가장 느린 알고리즘
• 모든 가능한 순열을 시도하여 풀고자 하는 경우

시간 복잡도 비교

상수 시간 복잡도를 제외한 시간 복잡도를 비교하면 다음과 같습니다. 물론 *n* 값이 충분히 클 경우를 가정 했을 때입니다.

로그 ＜ 선형 ＜ 로그 선형 ＜ 2차 ＜ 지수 ＜ 팩토리얼

 

마무리

 이 번 글을 통하여 알고리즘 성능을 표현하는 방법인 빅 오 표기법과 대표적인 시간 복잡도를 알아봤습니다.