자료구조
자료구조란, 효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합이다.
복잡도
시간 복잡도
시간 복잡도 : 입력 크기에 대해 어떠한 알고리즘이 실행되는데 걸리는 시간
주요 로직의 반복 횟수를 중점으로 측정된다. 보통 빅오 표기법으로 표현
빅오 표기법
빅오 표기법 : 입력 범위 n을 기준으로 해서 로직이 몇 번 반복되는지 나타내는 것
입력 크기가 커질 수록 연산량이 가장 많이 커지는 항 (ex. 항) 과 달리 다른 것은 연산량의 증가가 미미하기 때문에 그것만 신경쓰면 된다.
시간 복잡도가 존재하는 이유
시간 복잡도를 더욱 효율적인 코드로 개선할 수 있는 척도로 이용
소요 시간: > >
즉, 보다는 , 보다도 을 지향해야 한다.
자료구조에서의 시간 복잡도
거의 평균 시간 복잡도와 최악의 시간 복잡도를 고려하면서 쓴다.
1) 평균 시간 복잡도
| 자료 구조 | 접근 | 탐색 | 삽입 | 삭제 |
|---|---|---|---|---|
| 배열 | O(1) | O(n) | O(n) | O(n) |
| 스택 | O(n) | O(n) | O(1) | O(1) |
| 큐 | O(n) | O(n) | O(1) | O(1) |
| 이중 연결 리스트 | O(n) | O(n) | O(1) | O(1) |
| 해시 테이블 | O(1) | O(1) | O(1) | O(1) |
| 이진 탐색 트리 | 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) |
2) 최악의 시간 복잡도
| 자료 구조 | 접근 | 탐색 | 삽입 | 삭제 |
|---|---|---|---|---|
| 배열 | O(1) | O(n) | O(n) | O(n) |
| 스택 | O(n) | O(n) | O(1) | O(1) |
| 큐 | O(n) | O(n) | O(1) | O(1) |
| 이중 연결 리스트 | O(n) | O(n) | O(1) | O(1) |
| 해시 테이블 | O(1) | O(n) | O(n) | O(n) |
| 이진 탐색 트리 | 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) |
백엔드 개발자 꿈나무