1. 계산 복잡도

• 알고리즘의 계산 복잡도는 시간 복잡도(time complexity)와 공간 복잡도(space complexity)로 나눌 수 있다.

시간 복잡도

• 알고리즘을 수행하는 데 얼마나 오랜 시간이 걸리는지를 분석한 것을 말한다.

공간 복잡도

• 알고리즘을 수행하는 데 얼마나 많은 공간(메모리/기억 장소)가 필요한지 분석한 것을 말한다.

빅 오 표기법

• 계산 복잡도를 표현하는 방법 중 하나로,
• 대문자 O 를 사용하여 계산 복잡도를 표현한다.
• 알고리즘을 수행할 때 최악의 경우를 가정한다.

2. 계산(시간) 복잡도 표현

O(1)

• 입력 크기 n과 계산 복잡도가 무관할 때

  예) 계산 공식 N*(N+1)/2를 이용한 1부터 N까지의 합

O(logn)

• 입력 크기 n의 로그 값에 비례하여 계산 복잡도가 증가할 때

  예) 이분 탐색

O(n)

• 입력 크기 n에 비례하여 계산 복잡도가 증가할 때

  예) 최댓값 찾기, 순차 탐색

O(nlogn)

• 입력 크기 n과 로그 n 값의 곲에 비례하여 계산 복잡도 가 증가할 때

  예) 병합 정렬

O(n^2)

• 입력 크기 n의 제곱의 비례하여 계산 복잡도가 증가할 때

  예) 선택 정렬, 삽입 정렬

O(2^n)

• 입력 크기가 n일 때 2의 n 제곱 값에 비례하여 계산 복잡도가 증가할 때

  예) 하노이의 탑

이미지 출처