[TIL] DAY 2 - 탐색(Search), Big-O Notation

선형 탐색(Linear Search) / 순차 탐색(Sequential Search)

• 배열의 길이에 비례하는 시간 소요 → O(n)
• 최악에는 모든 원소를 비교해야!

 

이진 탐색(Binary Search)

• 탐색하려는 배열이 이미 정렬되어 있을 때 적용
  • 크기순으로 정렬되어 있다는 성질 이용
• 한 번 비교할 때마다 배열이 반씩 줆 → O(log n)

 

Big-O Notation

• 알고리즘 복잡도(Complexity of Algorithms)를 표현
  • 선형 시간 알고리즘 - O(n)
    • 선형 탐색
  • 로그 시간 알고리즘 - O(log n)
    • 이진 탐색
  • 이차 시간 알고리즘 - O(n²)
    • 삽입 정렬(insertion sort)
  • 낮은 복잡도를 가지는 정렬 알고리즘
    • 병합 정렬(merge sort) - O(nlog n)

 

출처: 프로그래머스 스쿨 6강: 알고리즘 복잡도