TIL | 12.30.금 [CS 기초지식 | 시간 복잡도 / 공간 복잡도]

- 시간 복잡도

 

[시간 복잡도]

• 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석
• 알고리즘을 수행하는 데 연산들이 몇 번 이루어지는 지 (알고리즘의 절대적인 실행시간과는 다름)

 

 

[시간 복잡도 줄이기]

1. 제일 시간복잡도에 영향을 많이 끼치는 반복문의 숫자를 줄여야 한다.
2. 자료구조를 적절하게 이용
3. 알고리즘을 적절하게 이용하는 것 - 이진 탐색, 그리디 알고리즘, 정렬 알고리즘 등 효율적인 알고리즘을 학습해 본 뒤 적절히 이용

 

---

 

 

- 공간 복잡도

 

[공간 복잡도]

• 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석
• 프로그램을 실행시킨 후 완료하는 데 필요로 하는 자원 공간의 양

 

 

[공간 복잡도 줄이기]

1. 배열의 크기 → 줄이기
2. 얼마 만큼의 동적 할당인지 → 줄이기
3. 몇 번의 호출을 하는 재귀 함수 인지 → 호출 수 줄이기