그냥 게임개발자
자료구조 시간 복잡도 본문
많이 사용하는 자료구조의 시간복잡도를 정리해보겠습니다.
자료구조 | 참조 | 탐색 | 삽입 | 삭제 |
배열 | 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(logN) | O(logN) | O(logN) | O(logN) |
여기서 스택과 큐 같은 경우에는 가장 앞에 있는 요소를 참조한다고 하면 O(1)이지만 중간에 있는 요소면 스택과 큐는 순차접근이기에 O(N)이 걸립니다.
'내 개인적인 공부 > 자료구조' 카테고리의 다른 글
값에 의한 호출, 참조에 의한 호출 (0) | 2024.04.14 |
---|---|
primitive 타입, reference 타입 (0) | 2024.04.14 |
operator() (0) | 2024.04.14 |
구조체 우선순위 큐 (0) | 2024.04.14 |
priority queue (0) | 2024.04.14 |