[알고리즘] 시간복잡도 공부

알고리즘을 평가할땐 수행시간과 메모리 사용량을 기준으로 두게되는데 시간복잡도가 수행시간에 해당하며, 공간 복잡도가 메모리 사용량에 해당된다. 본 포스팅에선 이 중 시간복잡도에 대해 알아보려고 한다.

---

1. 시간복잡도

시간복잡도란 '입력된 데이터가 출력될 때까지 걸리는 시간'이다. 곧 알고리즘이 수행되는 시간이다.

시간복잡도가 낮으면 말그대로 입력부터 출력까지의 속도가 빠르며, 시간복잡도가 높이면 속도가 느려지게 된다.

 

 

 

2. 점진적 표기법 3가지

시간복잡도를 표기할때 3가지 표기법이 존재한다.

 

(1) 오메가(Ω) 표기법 > 제일 좋은 경우

(2) 세타(Θ) 표기법 > 평균적인 경우

(3) 빅-오(O) 표기법 > 제일 나쁜 경우

 

이 중 알고리즘이 최악일 경우에 평균과 가까운 성능으로 예측이 가능하므로

일반적으로 빅-오 표기법을 많이 사용한다.

 

 

3. 시간복잡도 단계

출저 : https://www.bigocheatsheet.com/

시간복잡도 단계는 위 그래프와 같으며 이를 정리해보면 아래와 같다.

 

 

 

4. 시간복잡도 계산

만약 input으로 문자열을 2개 입력받아 2개의 문자열이 같은지 판단하는 함수를 짠다고 가정해보자.

대소문자는 구별하지 않을 것이다. 이 코드에서 시간복잡도는 얼마가 될까?

설명을 위하여 위와 같이 간단히 짜보았다. 빅-오로 표기할 것이기 때문에 최악의 경우를 판단해보자.

위 for문은 두 문자열의 길이만큼 n번씩 2번 돌며 실행이된다.

그럼 여기서 상수와 같은 부분은 모두 제외하고, 총 O(n^2)라는 시간 복잡도를 가지게 되는 것을 확인할 수 있다.

---

여기까지 시간복잡도에 대한 공부를 마쳤다. 과제를 드리자면 위의 코드의 복잡도를 O(nlogn) 복잡도 보다 낮게 만들 수 있다. 향후 함께 실습해보는 시간을 가지겠다.