시간복잡도(Time Complexity)
다양한 문제를 해결하기 위해 알고리즘을 생각하고 코드로 구현하는 과정에서 시간 복잡도를 고려한다는 것은 어떤 의미일까?
시간복잡도를 단순하게 풀이해보자면 다음과 같다.
Input의 변화에 따라 연산을 실행했을 때, 연산 횟수에 비해 시간이 얼만큼 걸리는가?
여기서 연산 횟수에 비한 시간은 통상적으로 사용되는 시간의 개념이 아니라 해당 알고리즘의 수행에 필요한 작업의 Step을 의미한다.
이는 상이한 실행 환경에서 성능에 차이가 있으므로, 일반적인 시간의 개념으로 표기할 경우 편차가 커질 수 있기 때문이다.
이때, 시간 복잡도는 점근 분석법을 통한 점근 표기법으로 표현된다.
점근적 분석법(asymptotic analysis)은 임의의 로직의 입력이 N -> ∞ 로 늘어날 때 어떠한 형태에 접근하는지 분석하는 것을 의미한다.
즉, 입력의 크기가 충분히 커졌을 큰 경우를 의미하고 이는 크기가 작은 경우 효율성을 논하기 어렵기 때문이다.
점근표기법의 유형
알고리즘을 효율적으로 만들기 위해 시간복잡도를 고려하고, 이는 해당 로직에 대한 점근적 분석을 통해 이루어진다.
최종적으로, 점근적 분석의 결과는 점근표기법을 통해 표현되는데 이는 크게 세 종류로 나눌 수 있다.
-
Big-Ω 표기법
: 해당 로직에서 최선의 경우를 의미하며, 점근적 하한선(Asymptotic lower bound)을 의미한다. -
Big-Θ 표기법
: 해당 로직에서 보통의 경우를 의미하며, 점근적 상한과 하한의 교집합(Asymptotic tighter bound)을 의미한다. -
Big-O 표기법
: 해당 로직에서 최악의 경우를 의미하며, 점근적 상한선(Asymptotic upper bound)을 의미한다.
Big-O 표기법
이 시간복잡도를 표기할 때 가장 자주 사용되는 것은 Big-O 표기법이다.
이는 빅오 표기법의 경우 코드가 실행되는 과정에서 최악의 경우를 고려하므로, 개발 과정에서 로직을 구현하는데 있어 문제를 인지하고 개선하는데 가장 효율적이기 때문이다.
그렇다면, Big-O 표기법에는 어떤 경우들이 존재할까?
