[C++] 자료구조 시간복잡도 정리

1. 랜덤접근과 순차적 접근

 

 

출처 : https://ko.m.wikipedia.org/wiki/파일:Random_vs_sequential_access.svg

 

vector, Array와 같은 배열은 랜덤접근이 가능해서 k번째 요소에 접근할 때 O(1)이 걸리며

연결리스트, 스택, 큐는 순차적 접근만이 가능해서 k번째 요소에 접근할 때 O(k)이 걸립니다.

 

• vector, Array → 랜덤접근 → O(1)
• linked list, stack, queue → 순차적 접근 → O(n)

 

참조를 많이 하는 것은 배열로 하는 것이 좋다.

 

• vector, Array → 삽입, 삭제 → O(n)
• linked list, stack, queue → 삽입, 삭제 → O(1)

 

데이터 추가와 삭제를 많이 하는 것은 연결 리스트가 배열보다 유리하다.

 

---

2. 자료구조 시간복잡도 정리

 

 

다양한 C++ 자료구조에 대한 주요 연산의 시간 복잡도를 아래에 요약하였습니다.

 

이 표는 각 데이터 구조가 제공하는 주요 연산의 평균적인 시간 복잡도를 보여줍니다.

 

단, 실제 성능은 구현 방법과 사용하는 데이터, 그리고 컴파일러 등 여러 요소에 의해 달라질 수 있습니다.

 

시간 복잡도는 컴퓨터의 계산 시간을 측정하는 방법으로, 'n'은 데이터의 크기를 나타냅니다.

 

복잡도가 낮을수록, 연산은 보통 더 빠르게 수행됩니다.

 

"Amortized"는 일반적으로 연산이 빠르지만 가끔 느려질 때 (예를 들어, 새로운 메모리를 할당할 때) 사용되는 용어입니다.

 

출처 : chatgpt-4.0

---