![[자료구조] 5.1. 복잡도](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbHUh5W%2FbtrNIKckirK%2FkPkfUdcieogZD6lUjEiaI1%2Fimg.jpg)
본 포스팅은 [면접을 위한 CS 전공지식 노트]의 내용을 참고하여 작성하였습니다.
5.1. 복잡도
복잡도는 시간 복잡도와 공간 복잡도로 나뉜다.
1) 시간 복잡도
문제를 해결하는 데 걸리는 시간과 입력의 함수 관계.
알고리즘의 로직이 얼마나 오랜 시간 걸리는지. 빅오 표기법*으로 나타냄.
(빅오 표기법*: 가장 영향을 많이 끼치는 항의 상수 인자와 나머지 항을 없앤 것. 예를 들어 10n^2+n의 시간이면 O(n^2)로 표기한다.)
필요한 이유: 효율적인 코드로 개선하는 데 쓰이는 척도.
2) 공간 복잡도
프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양.
정적 변수는 물론이고 재귀함수로 인해 동적인 공간을 계속해서 필요할 경우도 포함.
int a[1005];
위와 같은 코드를 예시로 들면, a 배열은 1005 * 4바이트의 크기를 갖게 된다.
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) |
'Study in SSAFY > 면접을 위한 CS 전공지식 노트' 카테고리의 다른 글
| [디자인 패턴] MVC 패턴 / MVP 패턴 / MVVM 패턴 (0) | 2022.10.12 |
|---|---|
| [디자인 패턴] 프록시 패턴 / 이터레이터 패턴 / 노출모듈 패턴 (0) | 2022.10.12 |
| [디자인 패턴] 싱글톤 패턴 / 팩토리 패턴 / 전략 패턴 / 옵저버 패턴 (0) | 2022.10.12 |
| [자료구조] 5.3. 비선형 자료 구조 (0) | 2022.10.05 |
| [자료구조] 5.2. 선형 자료 구조 (0) | 2022.10.05 |