자료 구조 : 효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합
복잡도 종류
- 시간 복잡도
- 공간 복잡도
5.1.1 시간 복잡도
빅오 표기법
- 시간 복잡도
- 문제를 해결하는 데 걸리는 시간과 입력의 함수 관계
- 알고리즘의 로직이 얼마나 오랜 시간 걸리는지 나타냄
- 보통 빅오 표기법으로 나타낸다.
- 빅오 표기법 : 입력 범위 n을 기준으로 로직이 몇 번 반복되는지 나타내는 것.
- 가장 많이 영향을 끼치는 항의 상수 인자를 빼고 나머지 항을 없앤다.
- 예를 들어 10n^2 + n이 걸린다고 할 때, O(n^2)
시간 복잡도의 존재 이유
- 효율적인 코드로 개선하는 데 쓰이는 척도가 됨
시간 복잡도의 속도 비교
- O(n^2)보단 O(n), O(n)보단 O(1)을 지향하자 !
5.1.2 공간 복잡도
- 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양
- 정적 변수로 선언된 것 말고도 동적으로 재귀적인 함수로 인해 공간을 계속해서 필요로 할 경우도 포함
5.1.2 자료 구조에서의 시간 복잡도
- 자료 구조를 쓸 때는 시간 복잡도를 잘 생각해야 한다.
Reference
주홍철 작가님의 '면접을 위한 CS 전공지식 노트'를 기반으로 작성되었습니다.
