알고리즘 복잡도 (공간 복잡도)

이해하기 쉽고, 장황하지 않은 자료를 기반으로 강의를 진행합니다.

잔재미코딩 소식 공유

좀더 제약없이, IT 컨텐츠를 공유하고자, 자체 온라인 강의 사이트와 유투브 채널을 오픈하였습니다
응원해주시면, 곧 좋은 컨텐츠를 만들어서 공유하겠습니다

● 잔재미코딩 유투브 오픈 [구독해보기]

11. 참고: 공간 복잡도¶

알고리즘 계산 복잡도는 다음 두 가지 척도로 표현될 수 있음
- 시간 복잡도: 얼마나 빠르게 실행되는지
- 공간 복잡도: 얼마나 많은 저장 공간이 필요한지

좋은 알고리즘은 실행 시간도 짧고, 저장 공간도 적게 쓰는 알고리즘

통상 둘 다를 만족시키기는 어려움
- 시간과 공간은 반비례적 경향이 있음
- 최근 대용량 시스템이 보편화되면서, 공간 복잡도보다는 시간 복잡도가 우선
- 그래서! 알고리즘은 시간 복잡도가 중심

Complexity:

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

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

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

본 자료와 같이 IT 기술을 잘 정리하여, 온라인 강의로 제공하고 있습니다

체계적으로 전문가 레벨까지 익힐 수 있도록 온라인 강의 로드맵을 제공합니다

자세히 알아보기 모든 강좌 보기

In [1]:

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

In [2]:

factorial(3)

Out[2]:

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

In [3]:

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