[자료구조] 프로그램 복잡도 - 공간복잡도, 시간복잡도

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 하여 큰 의미가 없음