math - 扫描文件以比较字符串。比较平均值

Question

我有两个文本文件，它们是两组字符串。First_file.txt(X 串) 和Second_file.txt(N 串)

First_file.txt

string1
string2
string3
...
stringX


Second_file.txt

string1
string2
string3
...
stringN

我以这种方式比较了这两个文件：我取了string1fromFirst_file并逐行扫描了Second_file,。如果我找到相同的字符串，请使用string2from中断并重新启动First_file。

所以最好的情况是第一行有匹配，最坏的情况是不匹配，所以我必须扫描整个文件。

我对比较的平均次数感兴趣：对N/2吗？

Answer 1

平均比较次数取决于文件 1 和文件 2 的长度。文件 1 中的每一行平均与文件 2 中的 N/2 个字符串进行比较。那么总平均比较次数将为 X * N/2（即X 文件 1 中的行数和 N 文件 2 中的行数）。