Maximum subsequence sum problem Algorithm Analysis

소개

C를 기반으로 maximum subsequence sum problem 알고리즘 4개를 분석

목차

1. Maximum Subsequence Sum Problem의 알고리즘 4개를 홈페이지에 올라와있는 5개의 데이터에 대하여 실행해보고, 그 결과와 결과에 대한 토의를 제출하시오.

본문내용

각각의 알고리즘의 running time을 보면, , , , 이다. 즉 네 번째 알고리즘의 running time이 가장 작음을 알 수 있고, 결과를 통해서도 확인할 수 있다. 하지만 N이 작을 때 두 번째 알고리즘과 세 번째 알고리즘에서 예상 밖의 결과를 보여주고 있음을 알 수 있는데, N이 커지게 되면 우리가 예상했던 결과와 일치하는 것을 알 수 있다. 결론은 big-oh function으로 정의된 running time을 가지고 어느 것이 더 빠르고 느린지 확실하게 얘기할 수 없다는 것이다. 왜냐면 N의 크기가 작을 때 어느 것이 더 빠를지 결정하는 것은 실제로 돌려보지 않고서는 알기 힘들기 때문이다. 각각의 알고리즘은 N의 크기가 커지면서 running time이 증가하지만, 알고리즘 4개를 가지고 비교했을 때, running time은 (알고리즘 4) < (알고리즘 3) < (알고리즘 2) < (알고리즘 1)이 됨을 알 수 있다.(N의 크기가 크다고 가정했을 때 이런 결과가 성립하게 된다.)

참고자료

· 없음