본 포스트는 '면접을 위한 CS 전공지식 노트'를 기반으로 공부한 내용을 정리한 포스트입니다.
자료구조 (data structure) : 효율적으로 데이터를 관리/수정/삭제/탐색/저장 할 수 있는 데이터 집합
복잡도
시간 복잡도
시간 복잡도 : 문제를 해결을 위해 걸리는 시간과 입력 값의 함수 관계
-
빅오 표기법
입력 값n을 기준으로 로직이 몇번 반복되는지 나타내는 것 -
시간 복잡도의 존재 이유
효율적인 코드로 개선하는데 사용되는 척도 -
시간 복잡도의 속도 비교
공간 복잡도
프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양
정적 변수로 선언된 것, 재귀함수와 같이 동적으로 공간을 필요로 하는 경우 포함
- 자료 구조의 평균 시간 복잡도
| 자료구조 | 접근 | 탐색 | 삽입 | 삭제 |
|---|---|---|---|---|
| 배열(array) | O(1) | O(n) | O(n) | O(n) |
| 스택(stack) | O(n) | O(n) | O(1) | O(1) |
| 큐(queue) | O(n) | O(n) | O(1) | O(1) |
| 이중 연결 리스트 (doubly linked list) | O(n) | O(n) | O(1) | O(1) |
| 해시 테이블(hash table) | O(1) | O(1) | O(1) | O(1) |
| 이진 탐색 트리(BST) | O(logn) | O(logn) | O(logn) | O(logn) |
| AVL 트리 | O(logn) | O(logn) | O(logn) | O(logn) |
| 레드 블랙 트리 | O(logn) | O(logn) | O(logn) | O(logn) |
- 자료 구조의 최악 시간 복잡도
| 자료구조 | 접근 | 탐색 | 삽입 | 삭제 |
|---|---|---|---|---|
| 배열(array) | O(1) | O(n) | O(n) | O(n) |
| 스택(stack) | O(n) | O(n) | O(1) | O(1) |
| 큐(queue) | O(n) | O(n) | O(1) | O(1) |
| 이중 연결 리스트 (doubly linked list) | O(n) | O(n) | O(1) | O(1) |
| 해시 테이블(hash table) | O(n) | O(n) | O(n) | O(n) |
| 이진 탐색 트리(BST) | O(n) | O(n) | O(n) | O(n) |
| AVL 트리 | O(logn) | O(logn) | O(logn) | O(logn) |
| 레드 블랙 트리 | O(logn) | O(logn) | O(logn) | O(logn) |
샐러드 싫음