들어가며
소프트웨어 개발의 세계에서 나는 물론 우리는 항상 최적화와 효율성을 고려한다.
코드를 작성할 때, 우리는 실행 시간을 줄이고 메모리 사용을 최소화하기 위해 노력하며, 이러한 목표를 달성하기 위해 알고리즘과 자료 구조를 선택하고 설계한다.
그렇다면 어떻게 우리는 이러한 최적화를 달성하고 코드를 더 빠르게 더 효율적으로 만들 수 있을까?
여기서 시간 복잡도와 공간 복잡도가 관련된다.
시간 복잡도와 공간 복잡도는 알고리즘과 데이터 구조의 효율성을 분석하고 측정하는 데 사용되는 중요한 개념이다.
이번 글에서는 이러한 복잡도의 개념에 대해 이해하고 학습하기 위해 이 글을 작성한다.
복잡도란?
시간 복잡도와 공간 복잡도를 알아보기 전에 복잡도에 대해 먼저 짚고 넘어가자.
복잡도(Complexity)는 컴퓨터 과학과 알고리즘 분야에서 사용되는 중요한 개념으로, 어떤 작업이나 알고리즘이 얼마나 복잡하고 어렵게 수행되는지를 나타낸다.
- 알고리즘의 성능, 효율성을 나타내는 척도
- 크게 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)로 나눌 수 있다.
- 각 알고리즘이 주어진 특정 크기의 입력(n)을 기준으로 수행시간(연산) 혹은 사용공간이 얼마나 되는지 객관적으로 비교할 수 있는 기준을 제시한다.
- 복잡도를 나타내는 방법으로는 점근 표기법으로 O(빅오), Ω(오메가), Θ(세타) 등이 있고, 주로 빅오와 세타 표기법이 많이 사용된다.
즉, 복잡도는 쉽게 말해 어떤 알고리즘이 효율적인지를 판단하는 척도라고 생각하면 된다.
시간 복잡도
시간 복잡도란 특정 크기의 입력을 기준으로 할 때 필요한 연산의 횟수를 나타낸다.
이름은 시간 복잡도이지만 실행 시간이 아닌 연산 횟수를 세는 이유는 다음과 같다.
- 모든 OS, IDE, 플랫폼에서 동일한 결과가 나오지 않는다.
- 실행 시간 측정을 위한 또다른 방법이 필요하다.
시간 복잡도를 줄이는 방법으로는 반복문의 숫자를 줄이고 적절한 자료 구조와 알고리즘을 사용해야 한다.
공간 복잡도
공간 복잡도란 프로그램 실행과 완료에 얼마나 많은 공간(메모리)이 필요한지를 나타낸다.
알고리즘을 실행시키기 위해 필요한 공간(space)는 두 가지로 나눌 수 있다.
- 알고리즘과 무관한 공간, 즉 고정 공간
- 코드가 저장되는 공간, 알고리즘 실행을 위해 시스템이 필요로 하는 공간 등
- 알고리즘과 밀접한 공간, 즉 가변 공간
- 문제를 해결하기 위해 알고리즘이 필요로 하는 공간. 변수를 저장하는 공간, 순환 프로그램일 경우 순환 스택(recursion stack) 등
공간 복잡도를 줄이기 위해서는 고정공간보다는 가변 공간을, 재귀적 코드 보다는 반복문으로 짜는 것이 효율적이다.
시간 복잡도 vs 공간 복잡도
시간 복잡도는 얼마나 빠르게 실행되는지, 공간 복잡도는 얼마나 많은 자원(메모리 공간)이 필요한지를 판단한다.
시간 복잡도와 공간 복잡도는 반비례하는 경향이 있어, 보통 알고리즘의 성능을 판단할 때는 시간 복잡도를 위주로 판단한다.
