시간 복잡도와 공간 복잡도
알고리즘의 성능을 이야기할 때 빠지지 않는 개념이 시간 복잡도와 공간 복잡도입니다. 두 개념이 무엇을 의미하고 서로 어떤 관계를 갖는지 정리해 보겠습니다.
시간 복잡도
- 알고리즘이 입력 크기에 대해 필요한 연산의 횟수를 나타냅니다.
- 연산의 횟수가 적을수록 좋습니다.
- 알고리즘의 실행 시간이 입력 크기에 비례하여 어떻게 증가하는지를 설명합니다.
공간 복잡도
- 알고리즘이 얼마나 많은 메모리를 사용하는지 나타내는 척도입니다.
- 프로그램이 실행될 때 사용되는 메모리의 양을 측정합니다.
비교
- 시간 복잡도와 공간 복잡도는 반비례하는 경향이 있습니다.
- 보통은 시간 복잡도로 알고리즘 성능을 판단합니다.
한 줄 요약
시간 복잡도는 연산 횟수, 공간 복잡도는 메모리 사용량을 나타내며, 둘은 반비례하는 경향이 있어 일반적으로 시간 복잡도를 기준으로 알고리즘 성능을 판단합니다.