시간복잡도
- 입력크기에 대해 알고리즘이 실행되는데 걸리는 시간이다.
- 빅오 표기법으로 반복횟수를 나타낸다.
- 빅오의 표기법에서는 상수항은 무시한다.
- 빅오의 표기법에서는 낮은 항은 무시한다.
- 빅오의 표기법에서는 계수는 무시한다.
- 만약 1부터 n까지 더하면? -> O(n)
- 1부터 2n까지 더하면? -> O(2n) = O(n)
- 수열의 n번째 항은 1부터 n까지 더한 수라고 할때 그 수열의 n번째 항까지의 덧셈은? -> n번째 항은 (n**2 + n)*(0.5)이고 이 수열의 n번째 항까지의 덧셈은 (2n***3+6n**2+4n)(1/12)이므로 O((2n***3+6n**2+4n)(1/12)) = O((1/6)n***3) = O(n***3) 이다.
int sum = 0;
for(int i=0; i<10; i++){
sum+=i;
}
공간복잡도(별로 안 중요함)
- 동적으로 공간이 필요할 때 주로 고려한다, 예를 들어 재귀함수가 있다.
자료구조에서 시간 복잡도
평균 시간 복잡도
| 자료구조 | 접근 | 탐색 | 삽입 | 삭제 |
|---|
| 배열(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) |
| 이중 연결 리스트(double 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) |
| 이중 연결 리스트(double 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) |
Discussion
- 최악, 평균, 최선의 경우 분석 방법 중에서 어떤 분석이 가장 정확한가?
- 최악, 평균, 최선의 경우 분석 방법 중에서 어떤 분석을 사용할 것인가?
더 자세히
개념 위주
예시 위주
