자료구조 별 Big O 시간 복잡도

1. Array (배열)

• 참조: O(1) (인덱스를 통한 직접 접근 가능).
• 탐색: O(n) (특정 값 찾기 위해 순차 탐색 필요).

2. Vector (동적 배열)

• 참조: O(1) (배열과 동일).
• 탐색: O(n) (배열과 동일).
• 삽입/삭제 (맨 끝/앞):
  • 끝: O(1) (끝에 추가하거나 삭제 가능).
  • 앞: O(1) (특정 구현에 따라 다를 수 있음).
• 삽입/삭제 (중간): O(n) (데이터를 이동해야 함).

3. Stack (스택)

• n번째 참조: O(n) (스택은 후입선출 구조로 특정 위치 접근이 느림).
• 가장 앞부분 참조 (Top): O(1) (스택의 꼭대기에 접근 가능).
• 탐색: O(n) (특정 값 탐색은 전체를 확인해야 함).
• 삽입/삭제: O(1) (스택의 맨 위에서만 작동).

4. Queue (큐)

• n번째 참조: O(n) (큐는 선입선출 구조로 특정 위치 접근이 느림).
• 가장 앞부분 참조 (Front): O(1) (큐의 첫 번째 원소에 빠르게 접근 가능).
• 탐색: O(n) (특정 값 탐색은 전체를 확인해야 함).
• 삽입/삭제: O(1) (맨 뒤에 추가하거나 맨 앞에서 삭제 가능).

5. Doubly Linked List (이중 연결 리스트)

• 참조: O(n) (특정 노드 접근 위해 순차 탐색 필요).
• 탐색: O(n) (특정 값 탐색도 순차적).
• 삽입/삭제: O(1) (노드 추가/삭제 시 참조만 변경하면 됨).

6. Map (맵, 예: 이진 탐색 트리)

• 참조: O(log n) (키를 기반으로 효율적 검색 가능).
• 탐색: O(log n) (이진 검색 기반 탐색).
• 삽입/삭제: O(log n) (트리 구조 업데이트). ​