알고리즘을 평가할 땐 수행시간과 메모리 사용량을 기준으로 두게되는데 시간복잡도가 수행시간에 해당하며, 공간복잡도가 메모리 사용량에 해당된다.

1. 시간복잡도

시간복잡도란 '입력된 데이터가 출력될 때까지 걸리는 시간'이며, 곧 알고리즘이 수행되는 시간임
시간복잡도가 낮으면 말 그대로 입력부터 출력까지의 속도가 빠르며, 시간복잡도가 높으면 속도가 느려지게 된다.

출처: https://saynot.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%8B%9C%EA%B0%84%EB%B3%B5%EC%9E%A1%EB%8F%84-%EA%B3%B5

2. 점진적 표기법 3가지

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

(1) 오메가 표기법(Ω) : 제일 좋은 경우
(2) 세타 표기법 (Θ) : 평균적인 경우
(3) 빅오 표기법 (O) : 제일 나쁜 경우

3. 시간복잡도 단계

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

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

4. 시간복잡도 계산

만약 input으로 문자열을 2개 입력받아 2개의 문자열이 같은지 판단하는 함수를 짠다고 가정해보자. 대소문자는 구별하지 않을 것이다. 이 코드에서 시간복잡도는 얼마가 될까?

위 for문은 두 문자열의 길이만큼 n번씩 2번 돌며 실행된다.
그럼 여기서 상수와 같은 부분은 모두 제외하고, 총 O(n^) 이라는 시간 복잡도를 가지게 되는 것을 확인할 수 있다.