알고리즘 성능 측정의 지표 - 빅오 표기법(Big-O Notation)

 

빅오 표기법

 

알고리즘의 성능을 측정하기 위한 가장 중요한 지표로 빅오 표기법이 존재한다.

 

빅오 표기법으로 시간 복잡도와 공간 복잡도를 계산할 수 있는데,

 

우선 빅오 표기법이 뭔지부터 알아보자.

 

Big-O Notation

 

위의 그래프가 빅오 표기법을 나타낸 그래프이다.

 

빅오 표기법은 크게 아래의 7가지로 나눌 수 있다.

 

O(1)

O(logN)

O(N)

O(NlogN)

O(N^2)

O(N^3)

O(2^N)

 

빅오 표기법이란 간단히 설명해서 O() 괄호 안에 원하는 식을 집어 넣는다.

 

그리고 식의 계수는 다 떼어 버린다.

 

왜냐하면 10000000000N이 아무리 크다 하더라도 N이 극한에 가까워지게 되면

결국 N^2보다 작아지는 순간이 오기 때문이다!

 

그렇게 해서 어떤 식이 더 규모가 큰 식인지를 빅오 표기법으로 구분하는 것이다. 

 

O(1) < O(logN) < O(N) < O(NlogN) < O(N^2) < O(N^3) < O(2^N)

 

위의 식은 그냥 외워버리자.

 

 

시간 복잡도

 

시간 복잡도란 빅오 표기법을 사용해서 알고리즘, 코드가 답을 도출하는 시간을 측정하는 것이다.

 

이때 사칙연산과 같은 기본적인 연산은 O(1)로 보면 된다.

 

또한 컴퓨터는 1초에 간단한 연산을 1억 번 정도 한다고 생각하면 되며,

 

언어마다 차이가 있을 수 있는데, C언어 같은 경우 0.5초, 파이썬 같은 경우 1초 정도로 생각하면 될 것이다.

 

즉, 우리는 알고리즘 혹은 코드를 짜면서 사용하는 알고리즘의 시간 복잡도를 비교해가며,

 

답을 도출하는 시간을 줄이는 방식으로 빅오 표기법을 활용하면 된다.

 

공간 복잡도

 

공간 복잡도란 똑같이 빅오 표기법을 사용해서 답을 도출하기 위해 필요한 메모리를 측정하는 것이다.

 

추가적으로 사실 현대 프로그래밍에 있어서 공간 복잡도보다 시간 복잡도가 더 중요하게 생각되는데,

 

그 이유는 과거에는 컴퓨터 메모리가 부족했지만, 현대에는 무어의 법칙으로 인해 메모리 성능이 폭발적으로 증가하고 있기 때문이다.