[ALGORITHM] 02. 시간 복잡도란?

알고리즘이 어떻게 실행 시간과 관련이 있는지를 나타내는 개념이며, 구체적으로는,

입력 크기가 증가함에 따라 알고리즘의 실행 시간이 어떻게 증가하는지를 나타내는 것이다.

시간 복잡도는 주로 빅 오 표기법(Big-O Notation)을 사용해 표현되며, 알고리즘의 성능을 상한선으로 나타낸다.

시간 복잡도를 평가할 때는 최악의 경우를 고려하며 최선의 경우나 평균적인 경우에 대한 시간 복잡도도 중요하지만,

최악의 경우를 고려하는 이유는 알고리즘이 어떤 입력에 대해서도 항상 특정 실행 시간을 보장하기 위함이다.

 

아래는 대표적인 빅 오 표기법의 예시이다.

빅 오 표기법	이름	설명
O(1)	상수 함수 (Constant Function)	입력의 크기와 무관하게 일정한 시간 소요
O(log n)	로그 함수 (Logarithmic Function)	입력 크기의 로그에 비례하는 시간 소요
O(n)	선형 함수 (Linear Function)	입력 크기에 비례하는 시간 소요
O(n log n)	로그 선형 함수 (Log-Linear Function)	대부분의 효율적인 정렬 알고리즘의 시간 복잡도 (퀵 정렬, 병합 정렬 등)
O(n²)	이차 함수 (Quadratic Function)	보통 2중으로 중첩된 반복문을 사용 (버블정렬)
O(n³)	삼차 함수 (Cubic Function)	보통 3중으로 중첩된 반복문을 사용
O(2ⁿ)	지수 함수 (Exponential Function)	실행 시간이 입력 크기의 지수에 비례해 증가 (부분집합 구하기)
O(n!)	팩토리얼 함수 (Factorial Function)	실행 시간이 입력 크기의 팩토리얼에 비례해 증가 (순열 만들기)

 

시간 복잡도는 알고리즘의 실행 시간을 표현하는 중요한 지표이지만, 항상 장점만 가지지는 않는다.

왜냐하면 앞서 말한 최악의 경우만 고려하기도 하고 알고리즘의 실행 시간을 추상적으로 표현하기에

특정 상황에서는 시간 복잡도가 높아 보이더라도 실제 실행 시간이 빠른 경우도 종종 나오기 때문이다.

거기다 공간 복잡도는 무시하기에 해당 알고리즘이 소비하는 메모리나 자원에 대한 정보는 고려하지 않아

공간 복잡도에 대한 정보를 알 수 없다.

그러므로 좋은 알고리즘을 판단할 때는 시간 복잡도 하나만으로 판단하는 게 아닌

다른 요소(문제의 특성, 요구 사항, 환경 등)들과 함께 종합적으로 판단해야 한다.