컴퓨터는 인간이 오랜 시간이 걸리는 문제도 순식간에 풀어낼 수 있습니다. 하지만 많은 문제들이 컴퓨터 조차도 오랜 시간이 필요한 문제들이 있습니다. 또한 컴퓨터는 인간 보다 많은 정보를 한번에 메모리에 저장해서 처리할 수 있습니다. 하지만 마찬가지로 어떤 문제들은 컴퓨터의 메모리로도 담아낼 수 없는 정보량을 필요로 하는 경우도 있습니다.

이러한 컴퓨터의 연산 속도와 정보 저장 공간에 대해 따지는 것이 시간 복잡도와 공간 복잡도입니다.

시간 복잡도

정의

해당 알고리즘이 최악의 경우 얼마만큼의 실행시간을 가지는가

입력량 N에 비례해서 연산의 횟수가 얼마나 되는지 표현

❗️ 정확한 연산의 횟수를 구하는 것이 아니라 N과의 비례관계를 파악하는 것이 중요!

Big-O 표기법

정의

입력량 N에 따라서 얼마나 연산이 증가하는가?

구하는 법

❗️ N이 무한대로 증가한다고 생각하자!

1. 상수 및 계수 제거
2. 가장 큰 항만 남기기

예시

15N^2 + 100N + 50000 회의 연산이 필요한 경우

1. 상수 및 계수 제거 → N^2 + N
2. 가장 큰 항만 남기기 → O(N^2)

공간 복잡도

정의

입력량 N에 비례해서 메모리를 얼마나 쓰는지 나타냄

시간 복잡도와의 관계

시간을 많이 사용하면 공간을 절약할 수 있고 공간을 많이 사용하면 시간을 절약할 수 있다!

→ Trade-off 관계

마치며...

시간 복잡도와 공간 복잡도에 대해 간단하게 알아봤습니다. 실제로 알고리즘 문제를 풀 때 두 가지 요소를 모두 고려하면서 풀어야합니다. 하지만 대부분 시간 복잡도만 신경을 쓰고 공간 복잡도는 크게 고려하지 않아도 된다고 합니다.