복잡도 분석

1부터 100까지의 합을 구해보자

1+2+3+...+99+100 을 하면 100번 연산을 해야한다.

(100*(1+100))/2 을 하면 갯수에 상관없이 3번만 연산을 하면된다.

당연히 아래 부분이 효율성이 높다고 할 수 있다.

 

효율성에는 공간적 효율성과 시간적 효율성이 있다.

공간적 효율성은 얼마나 많은 메모리 공간을 요구하는지를 나타내고

시간적 효육성은 얼마나 많은 시간을 요구하는지를 나타낸다

이 때 복잡도(complexity)가 높을 수록 효율성이 저하된다.

 

시간 볻잡도 분석이 하드웨어와 소프트웨어의 환경에 따라 달라진다.

따라서 객관적인 분석법이 필요하게 된다.

이때 나온 것이 복잡도의 점근적 표현이다

 

복잡도의 점근적 표현에는 Big-oh, big-omega, big-theta가 있다.

 

O(Big-oh) 의 표기

T(n): 실행시간

n은 실행 횟수

n0(처음 실행횟수) 보다 크거나 같은 모든 n에 대해서

T(n) <= c *f(n) 이면

T(n)=O(f(n))이라고 한다

(상수 c와 초기값 n0는 n과 독립적

- O-표기는 복잡도의 점근적 상한을 나타 낸다.

 

Ω(Big-Omega)표기

T(n) >= c*f(n)

T(n) = Ω(f(n))

- 복잡도는 점근적 하한을 의미

 

θ(Theta)

T(n)=O(f(n))이고 T(n) = Ω(f(n))일 때

T(n) = θ(f(n))이 성립한다.

c1 * f(n) <= T(n) <= c2 * f(n)이 되는 c1, c2, n0가 존재 할 때만

T(n) = θ(f(n))이라고 한다. Ω <= θ <= O