[어서와! 자료구조와 알고리즘은 처음이지?] 03. 알고리즘 복잡도

본 문서는 어서와! 자료구조와 알고리즘은 처음이지? 강의를 보고 제 주관대로 정리한 글입니다.

---

알고리즘 복잡도 (Complexity of Algorithm)

• 시간 복잡도 (Time Complexity)
  • 문제의 크기와 이를 해결하는 데 걸리는 시간 사이의 관계
  • 평균 시간 복잡도 (Average Time Complexity)
    • 임의의 입력 패턴을 가정했을 때 소요되는 시간의 평균
  • 최악 시간 복잡도 (Worst-case Time Complexity)
    • 가장 긴 시간을 소요하게 만드는 입력에 따라 소요되는 시간
• 공간 복잡도 (Space Complexty)
  • 문제의 크기와 이를 해결하는 데 필요한 메모리 공간 사이의 관계

Big-O Notation

• 점근 표기법 중의 하나
• 알고리즘의 복잡도를 표현할 때 흔히 쓰임
• 입력의 크기가 n일 때, 얼마나 비례하는지 나타냄
• 계수는 별로 중요하지 않음

선형 시간 알고리즘 - O(n)

• e.g., n개의 무작위로 나열된 수에서 최댓값을 찾기 위해 선형 탐색 알고리즘을 적용
  • 최댓값 - 끝까지 다 살펴보기 전까지는 알 수 없음
  • Average case: O(n)
  • Worst case: O(n)

로그 시간 알고리즘 - O(logn)

• e.g., n개의 크기 순으로 정렬된 수에서 특정 값을 찾기 위해 이진 탐색 알고리즘을 적용

이차 시간 알고리즘 - O(n²)

• e.g., 삽입 정렬 (Insertion Sort)
  • Best case: O(n)
  • Worst case: O(n²)

보다 낮은 복잡도를 가지는 정렬 알고리즘

• e.g., 병합 정렬 (Merge Sort) - O(nlogn)
  • 정렬 문제에 대해 O(nlogn)보다 낮은 복잡도를 갖는 알고리즘은 없다는 게 수학적으로 증명됨