03c. 속도 기준 알고리즘 비교

반원_SemiCircle 2019. 5. 9. 00:15

속도로 분석하는 과정

생각보다 단순합니다.

복잡한 동전 지갑에서 눈을 가리고 500원을 찾는다고 가정하자. 이 때의 최선, 평균, 최악의 경우를 적어보면 다음과 같습니다.

최선의 경우를 분석해봤자 별 의미는 없겠죠. 단순히 "운이 좋았다"로 정리할 수도 있습니다.

결론적으로 말해서 알고리즘을 분석할 때 최악의 경우(Worst Case)으로 상황을 둡니다. 알고리즘 이용자 입장에서는 발생 빈도가 높은 평균의 경우(Average Case)를 성능 분석한 결과가 더 필요할 수 있습니다.

하지만 이건 결과만을 생각한 의견입니다. 과정을 고려하지 못했습니다. 평균의 경우의 성능 분석은 "어떤 상황이 평균으로 둘 것인가?"에 대한 이슈를 해결해야합니다. 알고리즘에 따라서 평균적인 상황을 정의하기 어렵거나 논란이 있을 수 있습니다.

그러나 최악의 경우는 대부분 정의가 가능하고, 확실한 정의가 힘들더라도 각 정의의 오차가 적습니다.

처리할 데이터의 개수에 따라 연산 횟수가 급격하게 늘어나서 알고리즘의 속도가 느려질 수 있습니다.

어느 알고리즘이 좋다고 할 수 있을까요? 두 선이 만나기 직전까지는 알고리즘A가 좋고, 그 이후는 알고리즘 B가 성능이 좋네요.

그럼 이렇게 생각할 수 있습니다. "초반에는 알고리즘 A를 사용하고, 그 이후엔 알고리즘 B를 사용한다!" 그렇다면 알고리즘을 2개 구현해야겠네요?

보통 알고리즘은 하나 구현합니다. 또한 데이터가 적을 때 이득은 적은 편이지만 데이터가 많을 때의 손해는 굉장히 큽니다. 따라서 이 경우엔 "알고리즘 B가 A보다 좋다"라고 평가할 수 있습니다.

하지만 프로그램 특성상 처리할 데이터가 적거나, 두 알고리즘이 만나는 지점보다 적은 데이터만 관리한다면? 그 때는 알고리즘 A를 사용해야겠죠.