시간 복잡도 vs 공간 복잡도

썸네일 출처: https://ledgku.tistory.com/33

시간 복잡도

정의

알고리즘의 절대적인 실행 시간은 하드웨어, 소프트웨어 환경에 따라 천차만별이다

• 알고리즘의 절대적인 실행 시간이 아닌, 수행되는 연산의 숫자를 의미
• 연산의 실행 횟수는 상수가 아닌 입력되는 데이터의 개수 n에 따라 변화
• 수식으로는 T(n)으로 표기

빅오 표기법

2n이나 4n이나 거기서 거기.
n과 n제곱은 유의미한 차이.

• 시간 복잡도를 표기하는 방법
• 시간 복잡도 함수에서 불필요한 연산(e.g 하나의 루프 제어문 연산)을 제거하여 알고리즘 분석을 간편하게 한다
• 우리가 빅오 표기법으로 나타내고자 하는 것은 연산의 정확한 실행 횟수가 아니라
  연산 횟수의 증가 추세를 나타내는 일반적인 데이터
• 따라서 연산 횟수가 2n + 2이든 10n + 100이든 빅오 표기법으로 나타내면 O(n)이다
• 최선, 평균, 최악의 경우 중 최악의 경우를 척도로 삼는다

공간 복잡도

정의

• 프로그램을 실행시킨 후 완료하는 데 필요한 컴퓨터 자원 공간의 양
• 총 공간 요구 = 고정 공간 요구 + 가변 공간 요구
• 고정 공간 예시: 코드 저장 공간, 단순 변수, 상수 등
• 가변 공간 예시: 함수의 순환 호출 시 요구되는 추가 공간 등

시간 복잡도 vs 공간 복잡도

얼마나 빠르게 실행되는가? vs 얼마나 많은 컴퓨터 자원이 필요한가?

• 따라서 좋은 알고리즘이란 "빠른 시간 내에 컴퓨터 자원을 적게 사용하는 것"
• 그러나 시간 복잡도와 공간 복잡도는 반비례하는 경향이 있다
• 결론적으로 좋은 알고리즘을 판단하는 주요 척도는 시간 복잡도가 된다