알고리즘의 성능 분석

성능 분석을 위해서는 직접 알고리즘의 실행 속도를 측정하는 방식을 통해 하지 않고, 이론적 모델의 실행 속도를 측정함

비용을 많이 발생시키는 instruction(ex. 비교)이 결국 알고리즘의 시간을 결정지음

 

• worst case :  가장 나쁜 상황에서 걸리는 시간
• average case : 평균적인 상황에서 걸리는 시간. 하지만 이를 분석하는 것이 어려워서 주로 worst case를 통해 시간측정을 함

 

T(n) : 문제 사이즈가 n일때 걸리는 시간

성능 측정에 있어서 너무 작은 문제 사이즈는 don't care이고 어느 정도 이상의 크기만 고려 대상

 

시간을 3n^3+90n^2-5n+600이런 식으로 계산할 수 있지만 이렇게 정확하게 계산할 필요는 없고 n이 엄청 커질 것으로 생각해서 가장 영향을 크게 끼치는 제일 높은 차수를 제외한 나머지를 무시함.

=> 결국 전체적 비용을 좌우하는 것은 가장 큰 차수!

 

invariant

어떤 알고리즘에서 변하지 않는, 항상 만족하는 성질.

invariant가 무엇이 될 지를 고민해보아야 함