시간 복잡도 vs 공간 복잡도

aiden·2020년 10월 26일
0

알고리즘

목록 보기
1/6
post-thumbnail

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

시간 복잡도


정의

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

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

빅오 표기법

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

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

공간 복잡도


정의

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

시간 복잡도 vs 공간 복잡도


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

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

0개의 댓글