CS 어디까지 알고있니?_ep.5 (선형탐색)

나라리야·2021년 7월 27일
0

CS_study

목록 보기
17/18
post-thumbnail

많은 알고리즘 중에 첫번째로 선형탐색에 대해서 알아보자!
가장 단순!


선형 탐색 (Linear Search) 알고리즘

선형탐색은 원하는 원소가 발견될 때까지 처음부터 마지막까지 차례대로 탐색한다.
원하는 것을 찾을 때까지 모든 자료를 확인해야한다.

효율성 그리고 비효율성

선형 탐색 알고리즘은 정확하지만 아주 효율적이지 못한 방법이다.
리스트의 길이가 n이라고 헀을 때 최악의 경우 리스트의 모든 원소를 확인해야 하므로 n번만큼 실행되게 된다. 여기서 최악의 경우의 수는 찾고자하는 자료가 맨 마지막에 있거나 아예 없을 때 이다.
반대로 최고의 경우의 수는 찾고자 하는 자료가 맨 처음에 있을때이겠쥬?

선형탐색은 자료가 정렬되어 있지 않거나 그 어떤 정보도 없어 하나씩 찾아야 하는 경우에 유용하다.
다만, 주어진 상황의 조건이 명확하고 정렬이 가능한 상황이라면 최적의 알고리즘이 아니게되는 단점을 가지고 있다.

선형 탐색의 시간복잡도는 O(N) 이다.

profile
Code의 美를 추구하는 개발자 🪞

0개의 댓글