6강: 알고리즘의 복잡도

강의

"복잡도"는 자원이 얼마나 필요한가를 나타내는 측도입니다.

- 시간 복잡도 : 문제의 크기와 해결하는데 걸리는 시간 사이의 관계

- 공간 복잡도 : 문제의 크기와 이를 해결하는데 필요한 메모리 공간 사이의 관계

 

"시간 복잡도"에는 여러 가지 종류가 존재합니다.

- 평균 시간 복잡도 : 임의의 입력 패턴을 가정했을 때 소요되는 시간의 평균

- 최약 시간 복잡도 : 가장 긴 시간을 소요하게 만드는 입력에 따라 소요되는 시간

 

복잡도를 표기할 때, 점근 표기법 중에 하나인 "Big-O Notation"을 이용합니다.

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

- 로그 시간 알고리즘 O(log n) : 이진 탐색, 병합 정렬(O(nlog n))

- 이차 시간 알고리즘 O(\(n^2\)) : 삽입 정렬