0. 개요
프로그래밍을 하면서 알고리즘의 효율을 측정할 수 있는 지표로는 크게 시간 복잡도와 공간복잡도가 있다. 알고리즘이 메모리를 얼마나 쓰는지 나타내는 것이 공간복잡도이고, 알고리즘이 문제를 해결하는데 걸리는 시간이 시간복잡도 이다.
과거에 하드웨어의 스펙이 좋지 않았을 적에는 이 두 가지 모두를 고려하면서 프로그래밍을 진행했지만, 최근 하드웨어의 성능이 좋아지고 나서부터는 공간복잡도 보다는 시간복잡도를 고려하여 프로그래밍을 하는 추세인 것 같다.
또한 시간복잡도와 공간복잡도는 트레이드오프 관계에 있다. 최근은 하드웨어 성능이 좋아짐에 따라 시간복잡도를 기준으로 알고리즘의 효율을 많이 측정하는 추세다.
그러므로 이 글에서는 공간복잡도 보다는 자료구조와 시간복잡도에 대한 것을 중점적으로 정리해 볼 계획이다.
1. 자료구조에 따른 시간 복잡도
점근 표기법
알고리즘의 성능을 입력 크기에 대한 함수로 표현하는 방법이다. 즉, 입력 크기가 증가함에 따라 알고리즘의 실행 시간이나 공간이 어떻게 증가하는지 알아보는 방법이다. 우리가 알고있는 빅오표기법이 이에 해당한다.
1) 빅오 표기법: 알고리즘의 최악의 경우를 표기
2) 빅오메가 표기법: 알고리즘의 최상의 경우를 표기
3) 빅세타 표기법: 알고리즘의 평균 실행시간을 표기
일반적으로 시간 복잡도를 이야기할 때에는 빅오표기법을 사용
자료 구조와 시간 복잡도
어떤 자료구조를 사용하느냐에 따라 같은 로직임에도 불구하고, 실행시간의 차이가 많이 날 수 있다. 그렇기 때문에 항상 시간복잡도를 고려한 자료구조의 선택이 필요하다. 자료구조를 선택할 때에는 평균과 최악의 시간복잡도를 고려하여 선택하는 것이 좋다.
자료구조의 평균 시간 복잡도
| 자료구조 | 접근 | 탐색 | 삽입 | 삭제 | 비고 |
| 배열 | 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) | head와 tail을 통해 순회 |
| 해시테이블 | O(1) | O(1) | O(1) | O(1) | hash 함수를 이용한 인덱스 접근 및 체이닝 |
| 이진탐색트리 | 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) |
자료구조의 최악 시간 복잡도
| 자료구조 | 접근 | 탐색 | 삽입 | 삭제 | 비고 |
| 배열 | 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) | head와 tail을 통해 순회 |
| 해시테이블 | O(n) | O(n) | O(n) | O(n) | hash 함수를 이용한 인덱스 접근 및 체이닝 |
| 이진탐색트리 | 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 전공지식 노트
'야놀자 테크스쿨 > JAVA 자료구조' 카테고리의 다른 글
| [면접을 위한 CS 전공지식 노트][자료구조] Stack(스택) (0) | 2023.08.03 |
|---|---|
| [면접을 위한 CS 전공지식 노트][자료구조] 연결리스트 LinkedList (0) | 2023.08.02 |
| [면접을 위한 CS 전공지식 노트][자료구조] Array(배열)와 ArrayList (0) | 2023.08.02 |
| [JAVA][자료구조] Java에서 Stack을 사용하는 방법 대해 알아보자! (0) | 2023.07.17 |
| [JAVA][자료구조] JAVA Queue 사용법. (0) | 2023.07.16 |
