시간 복잡 도 속사 표

상용 알고리즘 과 데이터 구조의 복잡 도 속사 표,
수색 하 다.
알고리즘
데이터 구조
시간 복잡 도
공간 복잡 도
 
 
고 르 게 하 다
최 악
최 악
깊이 우선 검색 (DFS)
Graph of |V| vertices and |E| edges - O(|E| + |V|) O(|V|)
범위 우선 검색 (BFS)
Graph of |V| vertices and |E| edges - O(|E| + |V|) O(|V|)
이분 찾기
Sorted array of n elements O(log(n)) O(log(n)) O(1)
궁 거 하여 찾다
Array O(n) O(n) O(1)
최 단 경로 - dijkstra, 작은 루트 로 우선 대기 열
Graph with |V| vertices and |E| edges O((|V| + |E|) log |V|) O((|V| + |E|) log |V|) O(|V|)
최 단 경로 - dijkstra, 무질서 배열 을 우선 대기 열 로 합 니 다.
Graph with |V| vertices and |E| edges O(|V|^2) O(|V|^2) O(|V|)
최 단 경로 - bellman - ford
Graph with |V| vertices and |E| edges O(|V||E|) O(|V||E|) O(|V|)
정렬
알고리즘
데이터 구조
시간 복잡 도
최 악의 경우 보조 공간의 복잡 도
 
 
최 적
고 르 게 하 다
최 악
최 악
빠 른 정렬
배열O(n log(n)) O(n log(n)) O(n^2) O(n)
정렬
배열O(n log(n)) O(n log(n)) O(n log(n)) O(n)
더미 정렬
배열O(n log(n)) O(n log(n)) O(n log(n)) O(1)
거품 정렬
배열O(n) O(n^2) O(n^2) O(1)
삽입 정렬
배열O(n) O(n^2) O(n^2) O(1)
정렬 선택
배열O(n^2) O(n^2) O(n^2) O(1)
통 정렬
배열O(n+k) O(n+k) O(n^2) O(nk)
기수 정렬
배열O(nk) O(nk) O(nk) O(n+k)
데이터 구조
데이터 구조
시간 복잡 도
공간 복잡 도
 
고 르 게 하 다
최 악
최 악
 
인덱스
찾다
끼어들다
삭제
인덱스
찾다
끼어들다
삭제
 
기본 배열O(1) O(n) - - O(1) O(n) - - O(n)
동적 배열O(1) O(n) O(n) O(n) O(1) O(n) 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(n) O(1) O(1) O(n) O(n) O(1) O(1) O(n)
메타제O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n) O(n) O(n) O(n) O(n log(n))
해시 시계- O(1) O(1) O(1) - O(n) O(n) O(n) O(n)
두 갈래 검색 트 리O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n) O(n) O(n) O(n) O(n)
피리 칼 나무- O(log(n)) O(log(n)) O(log(n)) - O(n) O(n) O(n) O(n)
B - 나무O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)
검 붉 은 나무O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)
스 트 레 칭 트 리- O(log(n)) O(log(n)) O(log(n)) - O(log(n)) O(log(n)) O(log(n)) O(n)
AVL 트 리O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)
쌓다
Heaps
시간 복잡 도
 
쌓 아 올리다
최대 값 찾기
최대 값 추출
Increase Key
끼어들다
삭제
합치다
 
링크 (정렬 됨)- O(1) O(1) O(n) O(n) O(1) O(m+n)
링크 (정렬 되 지 않 음)- O(n) O(n) O(1) O(1) O(1) O(1)
두 갈래 로 된 더미O(n) O(1) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(m+n)
이항적- O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n))
피 보 나치 더미- O(1) O(log(n))* O(1)* O(1) O(log(n))* O(1)
그림.
노드 / 사 이 드 관리
Storage
Add Vertex
Add Edge
Remove Vertex
Remove Edge
Query
인접 표O(|V|+|E|) O(1) O(1) O(|V| + |E|) O(|E|) O(|V|)
연관 표O(|V|+|E|) O(1) O(1) O(|E|) O(|E|) O(|E|)
인접 행렬O(|V|^2) O(|V|^2) O(1) O(|V|^2) O(1) O(1)
연관 행렬O(|V| ⋅ |E|) O(|V| ⋅ |E|) O(|V| ⋅ |E|) O(|V| ⋅ |E|) O(|V| ⋅ |E|) O(|E|)