(Data_Structure) Search 모음

1. Linear Search : Array or List의 처음부터 끝까지 순차적으로 탐색

시간 복잡도 : O(n) - 최악의 경우

 

2. Binary Search : Array or List가 정렬되어 있는 경우 중간 항목과 비교하면서 탐색

시간 복잡도 : O(log n) - 정렬되었을 때 최악의 경우

 

3. Hash Search : Hash function을 활용해 키와 값을 연결하는 방법으로 탐색

시간 복잡도 : O(1) - 평균의 경우

 

4. Tree Search : Binary Tree, Binary Search Tree, AVL, B-Tree 등 구조를 활용해 탐색

시간 복잡도 : O(log n) - Binary Search Tree 의 경우

 

5. Graph Search :

DFS (Depth-First Search)  : https://hyul-code.tistory.com/59

BFS (Breadth-First Search) : https://hyul-code.tistory.com/60

시간 복잡도 : O(V+E) - 최악의 경우