[CS] 자료구조 (시간 복잡도, 공간 복잡도)

 

1. 시간 복잡도

문제를 해결하는 데 걸리는 시간과 입력의 함수 관계

• 어떠한 알고리즘의 로직이 '얼마나 오랜 시간'이 걸리는지를 나타내는데 쓰임
• 보통 빅오표기법으로 나타냄
• 효율적인 코드로 개선하는 데 쓰이는 척도가 됨
• 평균, 최악의 시간 복잡도를 고려하면서 씀

 

* 용어 설명

빅오 표기법이란?
입력범위 n을 기준으로 해서 로직이 몇 번 반복되는지 나타내는 것

 

 

2. 공간 복잡도

프로그램을 실행시켯을 때 필요로 하는 자원 공간의 양

(정적 변수로 선언된 것 말고도 동적으로 재귀적인 함수로 인해 공간을 계속해서 필요로 할 경우도 포함)

 

 

 

공부기록용으로 남기는 블로그입니다.      

잘못 작성된 사항이 있다면 댓글 남겨주세요^^

 

 

출처
- 면접을 위한  CS 전공지식 노트 : 주홍철