2. Complexity Analysis

Complexity에는 Time과 Space가 있습니다. 알고리즘이 컴퓨터에서 동작하는 한, 컴퓨팅 자원을 사용하게 되고 그 중 영향력이 높은 것이 시간과 요구하는 공간이기 때문입니다. 자세한 설명은 다시 포스팅하겠습니다.

 

Asymptotic Function Growth

두 프로그램의 Time complexity를 비교하기 위한 방법으로 사용하는 것입니다. 총 5가지 O, o, $\Omega$, $\omega$, $\Theta$가 있습니다.

 

Upper Bound

Big oh, O

Small oh, o

 

Lower Bound

Big omega, $\Omega$

Small omega, $\omega$

 

Tight Bound

Tight bound complexity, $\Theta$

 

According to Input

알고리즘이나 문제의 bound를 구하는 문제는, 알고리즘이 input에 따라 어떤 성능을 보여주는지와 같게 됩니다. Upper bound는 worst case가, Lower bound는 best case가 되는 거죠. 또한 모든 input에 대한 time complexity를 구해서 평균을 내주게 되면, average case에 대한 time complexity가 구해지게 됩니다.

 

상황에 따라 알맞은 알고리즘을 선택해 사용할 수 있어야 합니다.