시간 복잡도와 Big O

시간 복잡도와 Big O

 

프로그램의 성능에는 다양한 변수들이 영향을 미친다. 하드웨어의 성능, 운영체제의 성능, 컴파일러 최적화, 비동기 로직 등등... 그래서 프로그램의 성능을 시간 단위(분, 초)로 표시하는 것은 실제적으로 효용성이 없다. 좋은 로직으로 프로그램을 구현했다하더라도 다양한 변수에 의해 결과가 달라지기 때문이다.

그래서 시간 복잡도는 시간 단위로 표시하지 않고, 데이터의 양(Input)에 따라 동작의 수(Number of Operations)가 얼마나 증가하는지 를 표기하는 Big O 표기법을 사용한다.

 

Big O

 

 

Big O 표기법은 데이터의 양(Input)을 X축에 놓고 X값이 증가함에 따라 동작의 수(Number of Operations)가 얼마나 증가하는 지 상관관계를 보는 함수다. 표기는 대문자 O와 괄호가 만나 위의 그림과 같이 표기한다.

O(1)이 가장 시간복잡도가 작고, O(n!)이 가장 시간복잡도가 크다고 볼 수 있다.

 

• O(1) : 상수시간, 데이터의 양이 아무리 늘어나도 시간복잡도는 1이다.
• O(n) : 선형 시간, 데이터의 양이 늘어나는 만큼 1에 비례하여 동작의 수도 늘어난다.
• O(log n) : 로그 시간, 데이터의 양이 늘어나는 만큼 log 2 n에 비례하여 동작의 수가 늘어난다. 컴퓨터 과학에서 로그에 숫자가 생략되어 있을 때는 2라고 보면 된다.