시간복잡도?
알고리즘을 풀다보면 시간복잡도에서 들어 봤을 것이다.(애석하게도 나는 정말 나중에 듣고기도 했고 이제서야 알아보기 시작한다. ㅠㅠ) 시간복잡도는 입력값이 커짐에 따라 시간에대한 복잡도를 표기하는 방법이다.
시간 복잡도를 표기하는 방법
- Big-O(빅-오)
- Big-Ω(빅-오메가)
- Big-θ(빅-세타)
표기법에따라 시간 복잡도를 최악, 최선, 평균의 경우를 나타낸다. 그 중 빅-오 표기법은 최악의 경우를 고려한 것이고, 복잡도를 나타낼 경우 가장 대표적으로 사용된다. 빅오 표현법으로 각각의 시간 복잡도에 대해서 알아보자.
그림 출처 : flickr.com
O(1)
constant complexity라고 하고, 입력값이 증가하더라도 시간이 늘어나지 않는 것이 특징이다.
O(n)
Linear complexity라고 하며, 입력값이 증가하는 만큼 시간또한 선형적으로 증가하는 것을 의미한다. 여기서 알고리즘에따라 2n, 3n ...처럼 계수가 늘어날 수 있지만, n이 무한대로 갈 수록 의미가 퇴색되기 때문에 모두 O(n)으로 표기한다.
O(log n)
Logarithmic complexity라고 부르며, 빅-오 표기법중 O(1) 다음으로 빠른 시간 복잡도를 가진다. 대표적으로 Binary Search(이진검색)문제가 있다. 횟수를 거듭할 수록 검색해야 하는 데이터의 양이 2n만큼 줄어든다.
O(n2)
quardratic complexity라고 하며, 입력값이 증가함에 따라 시간이 n의 제곱의 비율로 증가한다.
O(2n)
exponential complexity라고 하며, 입력값이 지수에 따라 증가함을 보인다. 대표적으로 피보나치 수열이 exponetial 복잡도를 따른다. quardratic 복잡도보다 상승폭이 더욱 높다는 것이 특징이다.
O(n!)
factorial complexity라고 하며, 가장 심각한 시간 복잡도를 나타낸다.
마치면서
이외에도 여러가지 복잡도를 나타내는 형식이 있다. 대표적인 것만 올렸다. 위에 것만 우선 알면 다른 것들에 대한 이해는 어렵지 않을 것이다.
참조
[[10분 테코톡] 🙋♂️제이의 시간복잡도, 우아한Tech Youtube]
