[ TIL ] CS50 강의 노트(3)

부스트코스 <David J. Malan - 모두를 위한 컴퓨터 과학(CS50 2019)> 강의를 듣고 작성한 내용입니다.

검색(탐색) 알고리즘

1. 선형 검색(탐색)

• 배열의 인덱스를 처음부터 끝까지 하나씩 증가시키면서 방문하여, 그 값이 속하는지를 검사
• 자료가 정렬되어 있지 않거나, 그 어떤 정보도 없이 하나씩 찾아야 하는 경우에 유용.
• 정확하지만 효율적이지 못함.

2. 이진 검색(탐색)

• 배열이 정렬되어 있다면, 배열 중간 인덱스부터 시작하여 찾고자 하는 값과 비교하며, 그보다 작은 값이 저장되어 있는 인덱스 또는 큰 값이 저장되어 있는 인덱스로 이동을 반복.

정렬 알고리즘

1. 버블 정렬

• 두 개의 인접한 자료 값을 비교하면서, 위치를 교환하는 방식.

2. 선택 정렬

• 배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환하는 방식.
• 교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가.

3. 병합 정렬(합병 정렬)

• 원소가 한 개가 될 때까지 계속해서 반으로 나누다가, 다시 합쳐나가며 정렬.
• 재귀적인 방식으로 구현됨.

알고리즘 표기법

1. Big O 표기법 : 실행 시간의 상한을 나타냄

2. Big Ω 표기법 : 실행 시간의 하한을 나타냄

알고리즘의 실행시간 비교

• 실행 시간의 상한

  O(n^2): 선택 정렬, 버블 정렬
  O(n log n): 병합 정렬
  O(n): 선형 검색
  O(log n): 이진 검색
  O(1)

• 실행 시간의 하한

  Ω(n^2): 선택 정렬
  Ω(n log n): 병합 정렬
  Ω(n): 버블 정렬
  Ω(log n)
  Ω(1): 선형 검색, 이진 검색