Time Complexity
- 프로그램에서 사용하는 알고리즘이나 자료구조에 따라 Time Complexity가 달라진다
자료가 적을때는 어느방법을 사용하더라도 비슷한 시간이 걸릴수 있지만 자료가 많아질 수록
그 차이는 기하 급수적으로 증가할수 있기 때문에 어떤 알고리즘, 자료구조를 사용해야할지를 알고 결정하는것은
프로그래머로써 꼭 필요한 능력이다. - Big-O 표기법
- 시간복잡도에서 상수를 때고 표기한다 ex) 3n^2 -> O(n^2), 4 -> O(1)
- 시간복잡도는 항상 최악의 경우로 표기한다.
- Data Structure whit Time Complexity
| Lookup | Assign | Insert | Remove | Find | |
| Array | O(1) | O(1) | O(n) | O(n) | O(n) |
| Lined Lists | O(n) | O(n) | 위치를 알면: O(1) 위치를 모르면: O(n) |
O(n) | O(n) |
| Doubly Linked List | O(n) | O(n) | 위치를 알면: O(1) 위치를 모르면: O(n) |
O(1) | O(n) |
- Array: 보는것과 수정에 효과적인 자료구조
- Lined Lists: 입력에 효과적인 자료구조
- Doubly Linked List: Linked list 보다 삭제가 효율적인 자료구조, (공간은 더 차지한다.)
'개발 > 자료구조' 카테고리의 다른 글
| 자료구조 Graph, Tree, BST (0) | 2020.09.07 |
|---|