[자료구조] 공간복잡도, 시간복잡도, 성능평가
·
전공/자료구조
공간복잡도 프로그램을 실행시켜 완료하는 데 필요한 메모리 양 - 고정 부분: 보통 명령어 공간, 단순 변수, 집합체, 상수를 위한 공간 - 가변 부분: 특정 문제의 인스턴스에 따라 크기가 달라지는 변수, 순환 스택 공간 프로그램 P의 공간 요구 S(P) = c + Sₚ - c: 상수 - Sₚ: 인스턴스 특성 예시 float Abc(float a, float b, float c) { return a+b+b*c+(a+b-c)/(a+b)+4.0; } // Sₚ = 0 inline float Sum(float *a, const int n) { float s=0; for(int i=0;i