linear search 는 for 문을 사용하여 배열에서 해당값을 찾는 알고리즘 입니다.
이는 기본적인 알고리즘으로 보통 많이 사용합니다.
하지만 시간복잡도가 O(n) 이므로 시간이 오래 걸릴 수 있습니다.
이를 해결하기 위해 binary search(이진탐색)가 나왔습니다.
배열의 처음과 마지막의 중간값을 비교하여 찾는값이 중간값보다 크면 중간 ~ 끝까지
중간~끝 의 중간보다 크면 그 중간의 오른쪽으로 넘어가는 방법입니다.
따라서 시간이 1/2씩 단축되는 효과가 있습니다.
이를 시간복잡도로 나타내면 (1/2)^k * n 이므로 O(log n) 이 됩니다.
*주의 : 이진탐색은 쪽 정렬된 배열에서 사용하세요!!!
참조: https://www.youtube.com/watch?v=J3hM7xE9aFc
https://www.youtube.com/watch?v=ajINjfQL9gQ
이진 탐색과 시간 복잡도 분석 (Binary Search and its Time Complexity Analysis)
오늘 다뤄 볼 주제는 바로 "이진 탐색(Binary Search)" 입니다. 높은 효율을 자랑하며 실제로 자주 쓰이는 알고리즘인데요, 과연 이진 탐색이라는 게 무엇인지 한번 알아봅시다! - 이진 탐색(Binary Searc
jwoop.tistory.com
'cs > cs지식' 카테고리의 다른 글
| DFS 와 BFS (0) | 2023.06.27 |
|---|---|
| Linked List (연결 리스트) (0) | 2023.06.20 |
| BIG-O 표기법 (0) | 2023.06.20 |