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

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

좋은 웹페이지 즐겨찾기