[DS&Algorithm] 각 자료구조간 대표 시간 복잡도 정리

출처: leetcode cheatsheet

 

코딩 인터뷰를 하며 기초적인 질문은 바로 알고리즘의 시간 복잡도를 분석하는것!

 

시간 복잡도 종류

시간 복잡도는 크게 O(Big-O), Ω(Omega), Θ(Theta) 라고 불리는 3가지의 표기법이 있으며 Omega 는 최상의 경우로 예를 들면 찾고자하는 숫자가 바로 앞에 놓여있는것이고  Theta는 중간 경우라 생각하면되고 전반적으로 쓰이는 Big-O는 최악의 경우의수로 알고리즘에 최악의 경우의 수를 가정하는 이론이다.  => Big-O 를 구한다 생각.

 

출처: 릿코드

위 도표는 표현법에따른 시간 복잡도를 나타낸것이고 O(1) -> O(log n) -> O(n) -> O(n log n) -> O(n^2) -> O(2^n) -> O(n!) 순으로 시간 복잡도 즉, 계산하는데 시간이 무진장 걸린다. 

 

아래는 각 대표 자료구조의 기능에따른 시간 복잡도를 서술하겠다.

---

배열 (동적 배열/리스트)

n = arr.length이 주어졌을 때,

• 끝 부분에 원소 추가 또는 삭제: O(1)
• 임의의 인덱스에서 원소 추가 또는 삭제: O(n)
• 임의의 인덱스에 접근 또는 수정: O(1)
• 원소의 존재 확인: O(n)
• 두 개의 포인터: O(n⋅k), 여기에서 k는 각 반복에서 수행되는 작업으로 슬라이딩 윈도우를 포함
• 접두사 합 구성: O(n)
• 접두사 합이 주어졌을 때 하위 배열의 합 찾기: O(1)

---

문자열 (불변)

n = s.length이 주어졌을 때,

• 문자 추가 또는 삭제: O(n)
• 임의의 인덱스에서 요소 접근: O(1)
• 두 개의 문자열 연결: O(n+m), 여기에서 m은 다른 문자열의 길이
• 부분 문자열 생성: O(m), 여기에서 m은 부분 문자열의 길이
• 두 개의 포인터: O(n⋅k), 여기에서 k는 각 반복에서 수행되는 작업으로 슬라이딩 윈도우를 포함
• 배열, 스트링빌더 등으로부터 문자열 구성: O(n)

---

연결 리스트

n은 연결 리스트의 노드 수일 때,

• 포인터가 가리키는 위치 이전에 원소 추가 또는 삭제: O(1)
• 포인터가 가리키는 위치에서 원소 추가 또는 삭제: 이중 연결 리스트인 경우 O(1)
• 포인터가 없는 임의의 위치에 원소 추가 또는 삭제: O(n)
• 포인터가 없는 임의의 위치에서 요소에 접근: O(n)
• 원소의 존재 확인: O(n)
• i와 j 사이를 반전: O(j−i)
• 사이클 감지: 빠른-느린 포인터 또는 해시 맵을 사용하여 O(n)

---

해시 테이블/사전

n = dic.length이 주어졌을 때,

• 키-값 쌍 추가 또는 삭제: O(1)
• 키의 존재 확인: O(1)
• 값의 존재 확인: O(n)
• 키에 연결된 값을 접근하거나 수정: O(1)
• 모든 키, 값 또는 둘 다에 대해 반복: O(n)

참고: O(1) 작업은 n에 상대적으로 일정. 실제로 해싱 알고리즘은 비용이 많이 들 수 있음. 예를 들어, 키가 문자열인 경우 문자열의 길이인 m을 사용하여 O(m)이 소요. 작업은 해시 맵의 크기에 상대적으로 일정한 시간이 소요됨.

---

집합

n = set.length이 주어졌을 때,

• 원소 추가 또는 삭제: O(1)
• 원소의 존재 확인: O(1)

---

스택

스택 작업은 구현 방식에 따라 다름. 스택은 pop 및 push만 지원하면 됨. 동적 배열로 구현된 경우:

n = stack.length이 주어졌을 때,

• 요소를 푸시: O(1)
• 요소를 팝: O(1)
• 피크 (스택 상단의 요소 보기): O(1)
• 임의의 인덱스에서 요소에 접근 또는 수정: O(1)
• 원소의 존재 확인: O(n)

---

큐

큐 작업은 구현 방식에 따라 다름. 큐는 dequeue 및 enqueue만 지원하면 됨. 이중 연결 리스트로 구현된 경우:

n = queue.length이 주어졌을 때,

• 요소를 인큐: O(1)
• 요소를 디큐: O(1)
• 피크(큐의 맨 앞 요소 보기): O(1)
• 임의의 인덱스에서 요소에 접근 또는 수정: O(n)
• 원소의 존재 확인: O(n)

---

이진 트리 문제 (DFS/BFS)

n은 트리의 노드 수일 때,

대부분의 알고리즘은 일반적으로 각 노드에서 수행되는 작업인 k에 대해 O(n⋅k) 시간이 소요. 이것은 일반적인 규칙일 뿐이며 항상 그렇지는 않음. 여기서는 BFS가 효율적인 큐로 구현된 것으로 가정.

---

이진 검색 트리

n은 트리의 노드 수일 때,

• 원소 추가 또는 삭제: 최악의 경우 O(n), 평균적으로는 O(logn).
• 원소의 존재 확인: 최악의 경우 O(n), 평균적으로는 O(logn).

평균적인 경우는 트리가 균형 잡혀 있을때며 각 깊이가 가득 채워진것에  가까운 경우임. 최악의 경우는 트리가 직선일 경우.

---

힙/우선순위 큐

n = heap.length이고 최소 힙을 다룰 때,

• 요소 추가: O(logn)
• 최소 요소 삭제: O(logn)
• 최소 요소 찾기: O(1)
• 원소의 존재 확인: O(n)

---

이진 검색

이진 검색은 초기 검색 공간의 크기가 n일 때 최악의 경우 O(logn)

---

기타

• 정렬: O(n⋅logn), 여기에서 n은 정렬되는 데이터의 크기.
• 그래프에서 DFS 및 BFS: 각 노드가 엣지를 반복하는 것 외에는 O(n⋅k+e). 여기에서 n은 노드 수이고 e는 엣지 수.
• DFS 및 BFS 공간 복잡도: 일반적으로 O(n). 그러나 그래프에서는 그래프를 저장하기 위해 O(n+e)이 필요할 수 있음.
• 동적 프로그래밍 시간 복잡도: 각 상태에서 수행되는 작업인 k의 작업이 필요한 상태 수인 n은 O(n⋅k).
• 동적 프로그래밍 공간 복잡도: 상태 수인 n이 O(n).