CS 기초/자료구조 및 알고리즘
[자료구조 및 알고리즘] CH9. Sorting and Searching
땅어
2020. 10. 26. 16:40
728x90
300x250
Sorting
Bubble sort
Selection sort
Insertion sort
Shell sort
Quick sort
Merge sort(분할->병합정렬)
Heap sort
각 sorting 알고리즘의 시간복잡도는?
- Bubble - O(n^2)
- Selection - O(n^2)
- Insertion - O(n^2)
- Shell sort
- Quick sort
- worst : O(n^2)
- best : O(nlogn)
- avg : O(nlogn)
- Merge sort
- Heap sort
Searching
Linear search는 언제 쓰면 좋은가?
- item이 sorted 되어있지 않거나 unsortable할 때
Linear search의 단점?
- 찾는 아이템이 없거나 뒤쪽에 있는 경우 비효율적
Binary search는 언제 쓰면 좋은가?
- item이 sorted 되어있을 때 효율적
Tree와 Graph에서의 searching 방법은?
- Tree
- Inorder
- Preorder
- Postorder
- Graph
- DFS
- BFS
각 searching 알고리즘의 시간복잡도는?
- Linear - O(n)
- Binary - O(logn)
- BST - O(logn)
728x90
300x250