참고한 책: 면접을 위한 CS 전공지식 노트 (http://www.yes24.com/Product/Goods/108887922)
5. 자료구조
5.1. 복잡도
5.1.1. 시간 복잡도
5.1.2. 공간 복잡도
5.1.3. 자료 구조에서의 시간 복잡도
p. 232
자료구조(data structure)
효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합
p. 233
5.1.1 시간 복잡도
문제를 해결하는 데 걸리는 시간과 입력의 함수 관계
어떠한 알고리즘의 로직이 '얼마나 오랜 시간'이 걸리는지를 나타내는 데 쓰임.
보통 빅오 표기법으로 나타냄.
빅오 표기법
입력 범위 n을 기준으로 해서 로직이 몇 번 반복되는지 나타내는 것
가장 영향을 많이 끼치는 항의 상수 인자를 빼고 나머지 항을 없앤 것.
시간 복잡도의 존재 이유
효율적인 코드로 개선하는 데 쓰이는 척도
p. 236
5.1.2 공간 복잡도
프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양.
정적 변수로 선언된 것 말고도 재귀적인 함수로 인해 공간을 계속해서 필요로 할 경우도 포함.
5.1.3 자료 구조에서의 시간 복잡도
보통 시간 복잡도를 생각할 때 평균, 그리고 최악의 시간 복잡도를 고려하면서 씀.
자료구조 평균 시간 복잡도(책에 있는 표)
| 자료구조 | 접근 | 탐색 | 삽입 | 삭제 |
| 배열(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) |
'CS 스터디' 카테고리의 다른 글
| 5.2 선형 자료 구조 (0) | 2023.06.25 |
|---|---|
| 4.7 조인의 원리 (0) | 2023.06.21 |
| 4.6 조인의 종류 (0) | 2023.06.21 |
| 4.5 인덱스 (0) | 2023.06.21 |
| 4.4 데이터 베이스의 종류 (0) | 2023.06.21 |
