알고리즘의 시간복잡도

알고리즘의 성능 평가

같은 문제를 풀어도 여러 방법의 알고리즘이 나옵니다.

여러 알고리즘 중 가장 효율적인, 성능이 좋은 방법을 택하는 것이 좋겠죠.

옛날에는 메모리가 비싸 메모리를 가장 적게 사용하는 것이 최적의 알고리즘이었습니다.

그러나 요즘은 메모리의 가격이 낮아져 알고리즘의 성능을 따질 때 가장 중요하게 보는 것은 '시간'입니다.

 

 

 

시간 복잡도

알고리즘의 성능은 시간으로 나타낼 수 있습니다. 다만 컴퓨터의 성능에 따라 차이가 있습니다.

그래서 시간이 얼마나 걸리는지를 알 수 있는 좀 더 객관적인 지표가 필요합니다.

따라서 보통 시간복잡도(Time complexity)라는 지표를 사용합니다.

 

여기서 말하는 시간복잡도는 입력 값에 따른 처리에 걸리는 시간을 말합니다. 

여기서 말하는 시간은 "연산의 실행 횟수"를 말합니다.

연산의 실행 횟수를 시간복잡도 함수 또는 시간복잡도라고 합니다.

 

예를 들어, 선택 정렬 알고리즘의 시간복잡도가 다음과 같다고 가정해보겠습니다.

여기서 입력 값 n은 정렬할 수의 개수를 나타냅니다. 

정렬할 수의 개수가 100개라면 식에 의해 아래와 같이 계산됩니다.

 

선택 정렬의 시간복잡도만으로는 어느 정도의 성능을 가지는지 파악할 수는 없지만,

퀵 정렬, 병합정렬 등과 비교한다면 위의 시간은 매우 긴 시간이라는 것을 알 수 있습니다.

 

 

점근적 표기: 빅-오 표기법

보통 알고리즘의 성능을 시간복잡도 함수 자체를 이용하여 비교하지 않습니다.

대신 빅-오 표기법 등 대표되는 점근적 표기방법을 사용합니다.

 

점근적 표기 방법을 간단히 설명하자면 시간에 가장 큰 영향을 주는 'n에 대한 항'만을 표시하는 것을 말합니다.

왜냐하면 입력값 n이 충분히 커졌다면 n에 대한 최고차항만 고려해도 충분하기 때문입니다.

또한, 마찬가지의 이유로 '점근적 표기'에서는 보통 최고차항에 붙은 계수(coefficient) 또한 무시합니다.

 

위의 예시를 가져와 설명하겠습니다.

2n^2과 3n이라는 2개의 항이 있지만, 최고차항은 2n^2입니다.

그리고 또 최고차항의 계수 2를 생략하여 빅-오 표기법으로 나타내면 다음과 같습니다.

 

 

여기서 O( ) 기호는 빅-오 방식의 점근적 표기법으로 나타냈다는 뜻입니다.

빅오 표기법은 가장 대표적인 점근적 표기 방법이므로

점근적 표기법으로 나타냈다고 하면 보통 빅오 표기법을 의미합니다.

 

n에 대한 최고차항으로 정리하면 아래와 같은 표가 나옵니다.

표의 왼쪽에 있을수록 성능이 좋고, 오른쪽에 있을수록 좋지 않은 알고리즘이 됩니다.

 

상수	로그	선형	선형 로그	제곱	지수(Exponential)	계승 (Factorial)
O( 1 )	O( log n )	O( n )	O( n log n )	O( n^2 )	O( 2^n )	O( n! )

 

아래의 그래프는 입력 값 n이 커짐에 따라 최고차항들이 어떻게 증가하는지 보여줍니다.

n의 값이 작을 때는 비슷한 시간이 걸리는 것처럼 보이지만, 

n이 커질수록 차이가 상당히 커진다는 것을 알 수 있습니다.

 

 

따라서 알고리즘의 시간복잡도를 빅오로 표기하였을 때

다음 순서를 참고하여 효율적인 알고리즘을 선택하는 것이 좋습니다.

 

1      <      log n     <      n    <      n log n      <      n^2      <      2^n      <      n!

 

각 시간복잡도별 알고리즘 예제

• 1: push, pop ...
• log n: Binary Tree, Binary Search ...
• n: for, Radix Sort ...
• n log n: Heap Sort, Merge Sort, Quick Sort(평균) ...
• n^2: Insert / Shell / Selection / Bubble Sort, Quick Sort(최악의 경우) ...
• 2^n: Fibonacci Sequence(재귀 사용시) ...