(CS50)-알고리즘 기초(선형탐색)

CS50 x edwith 강의를 들으며 정리한 공부 포스팅입니다.

그림출처

핵심 개념

• 선형 탐색

선형 탐색

• 원하는 원소가 발견될 때까지 처음부터 마지막 자료까지 차례대로 탐색.

효율성과 비효율성

• 선형 탐색 알고리즘은 정확하지만 매우 비효율적인 방법.
• 리스트의 길이가 n이라고 했을 때, 최악의 경우 n번만큼 실행 됨.
  • 최악의 경우란 찾으려는 자료가 맨 마지막에 있거나 리스트 안에 없는 경우.
• 따라서, 선형 탐색은 자료가 정렬되어 있지 않거나 어떤 정보도 없어 하나씩 찾아야 하는 경우에 유용함.

[선형탐색예시]