파일을 스캔하여 문자열을 비교합니다. 비교의 평균

Question

두 개의 문자열 집합 인 두 개의 텍스트 파일을 가지고 있습니다. 내가 First_file에서 string1했다 그리고 난 라인으로 Second_file, 라인 스캔했습니다 First_file.txt (X 문자열) 및 Second_file.txt (N 문자열)

First_file.txt 

string1 
string2 
string3 
... 
stringX 


Second_file.txt 

string1 
string2 
string3 
... 
stringN 

나는이 방법이 두 파일을 비교했다. 같은 문자열을 발견하면 string2과 First_file에서 다시 시작하십시오.

가장 좋은 경우는 첫 번째 줄에 일치하는 항목이 있고 최악의 경우 일치하지 않으므로 전체 파일을 검색해야합니다.

나는 평균 비교 횟수에 관심이 있습니다 : 맞습니다 N/2?

Answer 1

평균 비교 횟수는 파일 1과 2의 길이에 따라 다릅니다. 파일 1의 각 줄은 파일 2의 N/2 문자열과 평균 비교됩니다. 그러면 평균 비교 횟수는 X * N이됩니다/2 (X는 파일 1의 행 수이고 N은 파일 2의 행 수임).