컴퓨터알고리즘개론 기말과제 A+ (문자열 알고리즘의 속도 비교)

소개

문자열 알고리즘의 속도 비교를 하는 visual studio 코드와 분석자료입니다.

brute-force, KMP, Boyer-Moore의 특성을 잘 보여줄 수 있는 문자열을 입력해서 활용하시길 바랍니다.

목차

1. 소스코드
2. 수행결과
3. 결과 분석

본문내용

제목: 문자열 알고리즘의 속도 비교

기능: 문자열 검색알고리즘을 brute-force, KMP, Boyer-Moore 중 선택이 가능, 선택은 1, 2, 3을 입력하는 방식

<중 략>

3. 결과 분석
문자열 검색알고리즘을 brute-force, KMP, Boyer-Moore 중 선택을 해서 검색할 수 있는 프로그램으로 입력한 패턴에 대한 패턴 일치 횟수, 수행시간을 출력한다.

사용한 패턴: ’am‘, ’church‘, ’demonstration‘

세 가지의 검색알고리즘의 패턴일치 횟수는 모두 동일했지만 수행시간에서 차이가 발생했다.

① brute-force
brute-force는 짧은 패턴인 ‘am’을 검색했을 때 패턴 일치 횟수가 매우 크더라도 수행시간은 ‘church’를 검색했을 때보다 적었다. 하지만 ‘demonstration’ 을 검색했을 때가 수행시간이 제일 적었는데 이는 패턴 일치 횟수가 매우 적고, 텍스트 파일에서 ‘a’의 개수가 ‘d’의 개수보다 두 배에 가까운 양인 것도 영향을 줬다. brute-force는 앞에서부터 차례대로 맞춰보기 때문에 특별한 특징이 없다.

참고자료

· 없음