[프로그래머스 알고리즘] 6강: 알고리즘 복잡도 (Complexity of Algorithm)

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

문제를 해결하는데 얼마만큼의 자원이 필요한가의 의미를 가지고 있다.

 

• 시간 복잡도 (Time complexity) : 문제의 크기와 이를 해결하는데 걸리는 시간과의 관계
  • 평균 시간 복잡도 (Average time complexity) : 임의의 패턴의 경우 소요되는 시간의 평균
  • 최악 시간 복잡도 (Worst-case time complexity) : 가장 시간이 많이 걸리는 패턴의 경우 소요되는 시간
• 공간 복잡도 (Space complexiry) : 문제의 크기와 이를 해결하는데 드는 메모리와의 관계

 

Big-O Notation 

점근 표기법 (Asymptotic notation) 중 하나

입력의 크기가 n 일때,

 O(log n) - 입력의 크기의 로그에 비례하는 시간 소요
 O(n) - 입력의 크기에 비례하는 시간 소요

 

1. 선형시간 알고리즘 : O(n)
   • 선형탐색 알고리즘
     • average case: O(n)
     • worst-case: O(n)
2. 로그 시간 알고리즘 : O(logn)
   • 이진탐색 알고리즘
     • average case: O(log n)
     • worst-case: O(log n)
3. 이차 시간 알고리즘 O(n^2)
   • 삽입정렬 (insertion sort)
     • best case: O(n)
     • worst-case : O(n^2)
4. 보다 낮은 복잡도를 가지는 알고리즘 O(nlogn)
   • 병합 정렬 (merge sort)
5. 꽤 복잡한 문제
   • 배낭 문제 (knapsack problem)