복잡도 분석

시간복잡도

• 시간복잡도는 프로그램 수행 시간을 분석하는 것이다.

• 반복문에 영향을 받고 결정된다. (반복문 하나를 1차항으로 본다)

빅오(BigO) 표기법에서 입력의 크기가 n일 때 주어진 프로그램의 수행 시간이 4n^4−7n^3+n^2 이라면 최고차항의 계수와 낮은 차수의 항을 제외시켜 `O(n4)` 와 같이 표기한다.

공간복잡도

• 공간복잡도는 프로그램의 메모리 사용량을 분석하는 것이다.

• 사용한 배열의 크기 * (해당 자료형의 크기) 로 계산한다.

• 보통 기타 지역 변수나 헤더 파일, 함수, 등을 생각해서 5~10MB 정도는 여유로 빼고 생각한다.