[자료구조] 프로그램 복잡도 - 공간복잡도, 시간복잡도
1️⃣ Program Complexity
- 정의
- 프로그램이 사용하는 메모리공간과 프로그램의 수행시간을 측정해서 성능을 드러내려고 함
✅ Space Complexity : S(P)
S(P) = Fixed space(c) + Variable space (Sp(I))
-
Fixed space (정적공간소모) : c
- input/output size에 무관한 공간
- 실제 프로그램 자체 코드 저장 공간
- 프로그램 내 선언된 변수들의 크기
- 크기를 미리 알 수 있는 물리적 공간 (ex. struct, char ..)
-
Variable space (동적공간소모) : Sp(I)
- input/output size에 종속된 공간
- 문제 해결과정 즉, run time에 서 instance에 의해 결정되는 공간
- Structured variables의 space + Recursion 에 의한 space
- instance가 어떻게 되었냐에 따라 변화
- ex. function call이 많을수록 공간 소모가 많이 발생
✅ Time Complexity : T(P)
T(P) = Compile time (Tc) + Run time(Tp)
ex. n개의 수를 더하고 빼는 Program의 runtime complexity
sum = a + b;
sum = sum - 1;
//덧셈 (1) + 뺄셈 (1) + 저장 (2) + 로드 (3) ⇒ T(P) = 1 + 1 + 2 + 3 = 7
💡 Run time (Execution time) 추정방법의 문제점은 Machine dependent 하여 큰 의미가 없음
Author And Source
이 문제에 관하여([자료구조] 프로그램 복잡도 - 공간복잡도, 시간복잡도), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@beneficial/자료구조-프로그램-복잡도-공간복잡도-시간복잡도저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)