취미와 밥줄사이

[ Algorithm ] 공간복잡도 본문

Python/알고리즘

[ Algorithm ] 공간복잡도

취미와 밥줄사이 2022. 3. 5. 11:59

공간 복잡도

  • 알고리즘 계산 복잡도는 다음 두 가지 척도로 표현할 수 있다.
    • 시간 복잡도: 얼마나 빠르게 실행되는지
    • 공간 복잡도: 얼마나 많은 저장 공간이 필요하는지
    • 좋은 알고리즘은 실행 시간도 짧고, 저장 공간도 적게 쓰는 알고리즘이다.
    • 시간과 공간은 반비례적인 경향이 있다.
  • 프로그램을 실행 및 완료하는데 필요한 저장공간의 양을 뜻함
  • 총 필요 저장 공간
    • 고정 공간(알고리즘과 무관한 공간): 코드 저장 공간, 단순 변수 및 상수(일정한 양의 메모리 공간)
    • 가변 공간(알고리즘 실행과 관련있는 공간): 실행 중 동적으로 필요한 공간
  • 입력값의 크기에 비례해서 알고리즘이 사용하는 메모리 공간을 의미
  • S(P) = c + Sp(n)
    • c: 고정공간
    • Sp(n)SP(n): 가변 공간
  • 고정 공간은 상수이므로 공간 복잡도는 가변 공간에 좌우된다.
  • 사용되는 변수의 개수
    • 인자 변수들을 일반적으로 제외하고 카운트

 

REFERENCE

https://juni-dev-log.tistory.com/125

 

[알고리즘] 공간 복잡도 'Space Complexity'

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

juni-dev-log.tistory.com

https://codingcocoon.tistory.com/112?category=1118526 

 

[파이썬][알고리즘] 공간 복잡도

공간 복잡도 좋은 알고리즘의 기준 시간 복잡도: 얼마나 빨리 실행이 되는지에 대한 기준 공간 복잡도: 얼마의 저장 공간이 필요한지에 대한 기준 시간과 공간은 반비례적인 경향이 있다. 컴퓨

codingcocoon.tistory.com

https://js0331.tistory.com/7

 

[codeit] Algorithm 공간 복잡도 (Space complexity)

저번 시간복잡도에 이어 이번에는 공간 복잡도에 대해 소개드리려고 합니다. 공간복잡도란? 공간 복잡도(Space Complexity)는 인풋 크기에 비례해서 알고리즘이 사용하는 메모리 공간을 나타냅니다.

js0331.tistory.com

https://stroot.tistory.com/101

 

알고리즘의 복잡도란? (1. 공간 복잡도)

복잡도가 낮을 수록 성능이 뛰어난 알고리즘입니다. 알고리즘의 복잡도(Complexity)는 두 가지 요소로 측정합니다. 1. 공간 복잡도 (Space complexity) 간단합니다. 사용되는 변수의 개수를 의미합니다.

stroot.tistory.com

https://velog.io/@codelog/%EA%B3%B5%EA%B0%84%EB%B3%B5%EC%9E%A1%EB%8F%84Space-Complexity

 

공간복잡도(Space Complexity)

알고리즘이 수행되는데 필요한 메모리의 총량!총 공간요구 = 고정 공간 요구 + 가변 공간 요구수식 : S(P) = c + Sp(n)입력과 출력의 횟수나 크기와 관계없는 공간을요구 즉, 코드 저장공간, 단순 변

velog.io

 

'Python > 알고리즘' 카테고리의 다른 글

[ Algorithm ] 선형검색( Linear Search), 이진검색(Binary Search)  (0) 2022.03.05
[Algorithm] 백준 2908번: 상수  (0) 2021.12.10
[Algorithm] 단어의 개수  (0) 2021.12.10
[Algorithm] 백준 1157번: 단어공부  (0) 2021.12.10
[Algorithm] 백준 2675번: 문자열 반복  (0) 2021.12.05
'Python/알고리즘' Related Articles more