알고리즘 분석과 복잡도 표기법(Big-O)

주로 공간복잡도 / 시간복잡도에 따른 분석이 이루어진다.

 

공간복잡도 분석이란?

입력 크기에 따라서 작업공간(메모리)이 얼마나 필요한 지 결정하는 절차.

 

시간복잡도 분석이란?

입력 크기에 따라서 단위 연산이 몇 번 수행되는지 결정하는 절차.
알고리즘이 실행되는 디바이스에 따라 문제 해결 시간이 다르다.

 

분석 방법의 종류

- 모든 경우 분석 (입력크기에 종속, 입력값과 무관하게 결과값 항상 일정)

- 최악의 경우 (입력크기, 입력값에 종속, 단위연산 수행 횟수 최대값 기준)

- 최선의 경우 (입력크기, 입력값에 종속, 단위연산 수행 횟수 최소값 기준)

- 평균의 경우

 

일반적으로 최악의 경우를 기준으로 알고리즘 개선하는 것을 목표로 한다.

 

복잡도 함수 표기법 (주로 Big-O 표기법 사용)

O( ) , o( ), Ω(), w(), θ()

 

Big-O 표기법 의미

주어진 복잡도 함수 f(n)에 대해서 g(n)->O(f(n)) 이면,

n >= N인 모든 정수 n에 대해서 0 <= g(n) <= c*f(n)이 성립하는 양의 실수 c와 음이 아닌 정수 N이 존재한다.

 

어떤 함수 g(n)이 O(n^2)에 속한다는 말은,

어떤 임의의 N값보다 큰 값에 대해서, n이 커짐에 따라 어떤 2차 함수 cn^2 보다는 작은 값을 가지게 된다는 것을 뜻한다.

 

(그래프 상에서는 아래에 위치)

-> 함수 g(n)은 어떤 2차 함수 cn^2 보다는 궁극적으로 좋다고(빠르다) 말할 수 있다.

 

어떤 알고리즘의 시간복잡도가 O(f(n))이라면,

입력의 크기 n에 대해서 이 알고리즘의 수행시간은 아무리 늦어도 cf(n)은 된다. (cf(n)이 점근적상한이다.) 

이 알고리즘의 수행 시간은 cf(n)보다 절대로 더 느릴 수 없다.

 

Small-o 표기법 같은 경우, 모든 양의 실수 c에 대해 성립해야 만족하는 걸 의미 (Big-O보다 더 깐깐한 조건?)