다양한 알고리즘 중, 탐색 알고리즘에 대해 알아보도록 하자.
정의
일반적인 탐색 문제란, 서로 다른 원소들로 이루어진 정렬된 리스트 a₁, a₂, ..., aₙ에서 어떤 원소 x를 찾거나, 그 원소가 리스트에 존재하지 않음을 판별하는 것이다.
구조
- 순서대로 정렬된 n개 원소의 리스트가 제공됨.
- 특정한 원소 x가 주어짐.
- x가 리스트에 존재하는지 확인해야하며, 리스트의 몇번째 인덱스에 존재하는지 알아내야함.
대표 알고리즘
Linear Search vs Binary Search
분명한 것은, 정렬된 데이터에 대해서는 이진 검색이 선형 검색보다 더 효율적이라는 점이다.
그렇다면, 알고리즘의 효율성은 무엇을 기준으로 판단할 수 있을까?
그 기준은 바로 Time(연산 횟수)과 Space(메모리 사용량)이다.
이는 각각 계산 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)를 의미하며,
알고리즘 성능을 평가하는 대표적인 척도다.
Let's learn about Searching Problems among various Algorithms.
Definition
The general searching problem is to locate an element x in an ordered list of distinct elements a₁, a₂, ..., aₙ, or determine that it is not in the list.
Structure
- Given a list of n elements that are sorted into a definite order (e.g., numeric, alphabetical)
- And given a particular element x,
- Determine whether x appears in the list, and if so, return its index(position) in the list.
Representative Algorithm of Searching Problems
Linear Search vs Binary Search
One clear fact is that binary search is more efficient than linear search when dealing with sorted data.
So how can we analyze the efficiency of an algorithm?
We can measure the Time (the number of elementary computations) and Space (number of memory cells)
These measures are called computational complexity and space complexity, respectively
