취미와 밥줄사이
[ Algorithm ] 공간복잡도 본문
공간 복잡도
- 알고리즘 계산 복잡도는 다음 두 가지 척도로 표현할 수 있다.
- 시간 복잡도: 얼마나 빠르게 실행되는지
- 공간 복잡도: 얼마나 많은 저장 공간이 필요하는지
- 좋은 알고리즘은 실행 시간도 짧고, 저장 공간도 적게 쓰는 알고리즘이다.
- 시간과 공간은 반비례적인 경향이 있다.
- 프로그램을 실행 및 완료하는데 필요한 저장공간의 양을 뜻함
- 총 필요 저장 공간
- 고정 공간(알고리즘과 무관한 공간): 코드 저장 공간, 단순 변수 및 상수(일정한 양의 메모리 공간)
- 가변 공간(알고리즘 실행과 관련있는 공간): 실행 중 동적으로 필요한 공간
- 입력값의 크기에 비례해서 알고리즘이 사용하는 메모리 공간을 의미
- 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
[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 |
