[알고리즘] 시간 복잡도(Time Complexity)

 알고리즘 로직을 코드로 구현할 때, 시간 복잡도를 고려한다는 것은 연산 횟수에 비해 시간이 얼마만큼 걸리는가를 생각하는 것이다. 즉, 문제를 해결하는 데 걸리는 시간과 입력의 함수 관계를 가리킨다.

 

 효율적인 알고리즘을 구현한다는 것은 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성한다는 것이다.

 

 시간 복잡도를 표기하는 방법은 Big-O, Big-Ω, Big-θ가 있으며, 이 세 가지 표기법은 각각 최악, 최선, 평균의 경우에 대하여 나타내는 방법이다. 주로 Big-O 표기법을 사용한다. 

 

 Big-O 표기법을 주로 사용하는 이유는 다음과 같다. 바로 프로그램이 실행되는 과정에서 소요되는 최악의 경우 시간까지 고려할 수 있기 때문이다. '최소 이 정도 시간 이상이 걸린다' 고려하기보다는 '최대 이 정도 시간까지 걸릴 수도 있다'를 고려하는 것이 그에 맞는 대응이 가능하다.

 

 

 

 

Big-O 표기법

 Big-O 표기법은 입력값의 변화에 따라 연산을 수행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가를 표기하는 방법이다.

 

 O(1)은 'constant complexity'라고 하며, 입력값의 크기와 관계없이 즉시 출력값을 얻어낼 수 있기 때문에 입력값이 증가하더라도 시간이 늘어나지 않는다. 즉, 실행시간이 가장 빠르다.

 

 O(n)은 'linear complexity'라고 하며, 입력값이 증가함에 따라서 시간 또한 같은 비율로 증가하는 것을 의미한다. 즉, 문제를 해결하기 위한 단계의 수와 입력값이 1:1 관계를 갖는다.

 

 O(log n)은 'logarithmic complexity'라고 하며, Big-O 표기법 중 O(1) 다음으로 빠른 시간 복잡도를 갖는다. 그리고 문제를 해결하는 데 필요한 단계들이 연산마다 특정 요인에 의해 줄어든다는 특성이 있다. up & down 게임을 예시로 생각하면 이해하기 쉽다.

 

 O(n^2)는 'quadratic complexity'라고 하며, 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미한다. 예를 들어 입력값이 1인 경우에 1초가 걸리던 알고리즘에 10이라는 값을 주었더니 100초가 걸리게 된다면, 이 알고리즘의 시간 복잡도는 O(n^2)라고 표현한다.

 

 O(2^n)은 'exponential complexity'라고 하며, Big-O 표기법 중 가장 느린 시간 복잡도를 갖는다. n이 늘어갈수록 걸리는 시간이 기하급수적으로 늘어나기 때문에 구현한 알고리즘의 시간 복잡도가 O(2^n)이라면 다른 접근 방식을 고민해 보는 것이 좋다.