[자바스크립트 알고리즘] 빅오 표현법과 시간 복잡도

* 본포스팅은 <쉽게 설명한 자바스크립트 알고리즘>에서 발췌한 내용으로 작성되었습니다.

 

 

✔  빅오 표현법과 시간 복잡도

알고리즘을 공부할 때 가장 처음 배워야 할 개념이자 첫 번째 관문은 빅오(Big-O) 표현법입니다. 빅오 표현법을 한마디로 정의하면 ‘최악의 경우가 나올 경우 얼마나 오래 걸리는가?’라 할 수 있습니다. 어려운 말로 상한 점근을 뜻합니다.알고리즘의 성능을 결정하는 요인은 내가 원하는 대로 데이터가 준비되는 경우가 아닌 극단적인 상황을 고려해야 합니다. 

 

빅오 표현법에서는 데이터 입력 조건을 n이라고 할때, n이 무한대로 커지는 경우를 고려해 표기하게 됩니다. 즉 빅오 표현법을 사용하면 알고리즘의 성능을 한눈에 알 수 있습니다.

 

 

빅오 표현법을 이해하기 위해 그림 1-1을 살펴봅시다. O(1)인 경우에는 데이터 입력과 상관없이 시간이 동일하게 소요됩니다. 즉 n값이 증가해도 소요되는 시간의 차이가 없는 경우를 뜻합니다.

 

 

코드 1-7을 무한히 실행시켜도 1회 요청을 할 때 소요되는 시간은 언제나 동일할 것입니다. 두 번째로 O(n)인 경우를 봅시다. O(n) 그래프는 y = x 그래프처럼 x축 값이 증가함에 따라 y축 값도 일정하게 증가합니다. 입력값이 증가하면 그만큼 소요되는 시간도 늘어나는 경우를 뜻합니다. 이에 해당하는 코드는 다음과 같습니다.

 

 

시스템상에 console.log( ) 명령을 호출하는 시간이 1ms(1,000분의 1초)라면, n값이 증가함에 따라 소요되는 시간도 동일하게 증가합니다. 코드로 생각해 보면 단순 반복문은 O(n) 복잡도를 가진다고 말할 수 있습니다. 세 번째로 O(n2) 그래프를 봅시다. n값이 증가함에 따라 소요 시간이 제곱으로 증가합니다. 이는 다음과 같이 표현할 수 있습니다.

 

 

n이 1인 경우에는 1번 console.log( )가 호출되지만, n이 2인 경우엔 4번, 3인 경우엔 9번 호출됩니다. 이처럼 O( ) 형태로 표현되는 빅오 표현법은 알고리즘이 n의 증가(데이터 입력)에 따라 시간이 얼마나 소요되는지 알 수 있습니다. 여기서 말하는 시간의 소요를 시간 복잡도라고 표현하고, O(n)은 1차 시간, O(n2)은 2차 시간이 소요된다고 표현합니다. 1차 시간과 2차 시간뿐만 아니라 다양한 형태의 알고리즘 성능이 존재합니다. 아래 표는 n에 따른 시간 증가를 나타냅니다.

 

 

위 표의 데이터 테이블은 코드를 쓸 때 재귀적 연산이 들어가면 안되는 이유를 증명하기도 하는데, 만약 여러분의 코드가 O(n3)이나 O(n!), O(2n)과 같은 형태로 표현된다면 실제 서비스가 운영되는 와중에 심각한 문제를 초래할 수 있을 겁니다.

 

---

 

 

《쉽게 설명한 자바스크립트 알고리즘》

예스24