Chapter 12. 기본 정렬 알고리즘: 참고, 공간 복잡도(Space Complexity)

• TOC {:toc}

이 글은 패스트 캠퍼스 기술면접 완전 정복 올인원 패키지 Online ’Chapter 12. 정렬: 참고, 공간 복잡도(Space Complexity)’의 강의내용을 정리하기 위해 강의 자료를 기반으로 작성한 글입니다.

강의 노트는 강의 구매자에게만 제공되는 자료이긴 하지만 잔재미 코딩의 11. 참고: 공간 복잡도에서 동일한 자료를 제공하고 있기 때문에 해당 자료를 기반으로 정리한 글을 작성해서 올립니다. 혹시 문제가 되는 경우 바로 내릴 예정이니 알려주시면 감사하겠습니다.

내용을 이해하기 위한 개인적인 설명이나 해석이 있을 수 있기 때문에 되도록 원문을 참고해주시길 바랍니다. 잘못된 부분이 있다면 댓글이나 그 외 편하신 방법으로 알려주시면 감사하겠습니다.

알고리즘 계산 복잡도는 다음 두 가지 척도로 표현될 수 있음

• 시간 복잡도: 얼마나 빠르게 실행되는지
• 공간 복잡도: 얼마나 많은 저장 공간이 필요한지

좋은 알고리즘은 실행 시간도 짧고, 저장 공간도 적게 쓰는 알고리즘이지만 모두 만족시키기는 어려움

• 시간과 공간은 반 비례적 경향이 있음
• 최근 대용량 시스템이 보편화하면서, 공간 복잡도보다는 시간 복잡도가 우선
• 그래서 알고리즘은 시간 복잡도가 중심

공간 복잡도도 대략적인 계산은 필요함

• 기존 알고리즘 문제는 예전에 공간 복잡도도 고려되어야 할 때 만들어진 경우가 많음
• 그래서 기존 알고리즘 문제에 시간 복잡도뿐만 아니라, 공간 복잡도 제약 사항이 있는 경우가 있음
• 또한, 기존 알고리즘 문제에 영향을 받아서, 면접 시에도 공간 복잡도를 묻는 경우도 있음

Complexity:

• expected worst-case time complexity: O(N)
• expected worst-case space complexity: O(N)

현업에서 최근 빅데이터를 다룰 때는 저장 공간을 고려해서 구현하는 경우도 있음

1. 공간 복잡도 (Space Complexity)

• 프로그램을 실행 및 완료하는데 필요한 저장공간의 양을 뜻함
• 총 필요 저장 공간
  • 고정 공간 (알고리즘과 무관한 공간): 코드 저장 공간, 단순 변수 및 상수
  • 가변 공간 (알고리즘 실행과 관련 있는 공간): 실행 중 동적으로 필요한 공간
• $S(P) = c + Sp(n)$
  • $c$: 고정 공간
  • $Sp(n)$: 가변 공간

빅 오 표기법을 생각해볼 때, 고정 공간은 상수이므로 공간 복잡도는 가변 공간에 좌우됨

2. 공간 복잡도 계산

• 공간 복잡도 계산은 알고리즘에서 실제 사용되는 저장 공간을 계산하면 됨
• 이를 빅 오 표기법으로 표현할 수 있으면 됨

공간 복잡도 예제 1

n! 팩토리얼 구하기

• n! = 1 x 2 x … x n
• n의 값에 상관없이 변수 n, 변수 fac, 변수 index만 필요함
• 공간 복잡도는 O(1)

공간 복잡도 계산은 실제 알고리즘 실행 시 사용되는 저장공간을 계산하면 됨

def factorial(n):
    fac = 1
    for index in range(2, n + 1):
        fac = fac * index
    return fac

# 테스트 코드
factorial(3) # 6

공간 복잡도 예제2

n! 팩토리얼 구하기

• n! = 1 x 2 x … x n
• 재귀함수를 사용하였으므로, n에 따라, 변수 n이 n개가 만들어지게 됨
  • factorial 함수를 재귀 함수로 1까지 호출하였을 경우, n부터 1까지 스택에 쌓이게 됨
• 공간 복잡도는 O(n)

def factorial(n):
    if n > 1:
        return n * factorial(n - 1)
    else:
        return 1