两字符串比较的快速算法，有什么思路？

我给你来点比较标准的算法解析吧：

对比特进行遍历算法：

最优时间复杂度为：O(1)

最差时间复杂度为：O(N)

对于两个随机字符串的期望时间复杂度是:O(2)。

但具体情况依据字符串分布空间不同而不同。

hash算法：

最差和最优时间，期望复杂度是:O(N）+O(l).

(l为hash的输出长度，当n小于l的时候，就会显得比较明显。）

其中取决于你的具体的算法的不同O(N)，前面系数可以为80到几万不等。

很显然hash算法不如直接对比特进行遍历。

不过提到了hash算法，我们不得不提到一下直接返回不相等代码的优越性：

首先就是时间复杂度为O(1)，比起hash算法遥遥领先。但是更为关键的是在大多数情况下正确率也比hash算法高。

我们假设hash算法的输出空间为

可以计算出hash算法的正确率是 。而当输入空间等于 直接返回不相等且正确的概率为

当出现一个 大于 的时候，直接返回不相等正确率比hash算法的正确率还要高。

很明显确定性算法的最优方法就是直接进行比特遍历，而概率性算法的最优算法就是直接返回错误。

当然也有两个折中的方案，就是随机抽取128个比特来进行比较的方案。

懂密码学的小伙伴可能就发现很类似于素性检测算法里面的不同算法的类型。确定性算法就是AKS算法，但是运行时间长，概率性算法就是米勒罗宾检测，但是多次运行可以保证出现非素数的概率很小。

（但是真实情况下的字符串比较算法下的输入空间不是一个随机分布的字符串空间，所以肯定存在问题）。

其次虽然hash算法看上去效率很不行，但是在多字符串比对中，假设输入是M条N长度的字符串。它的时间复杂度是O(M*N)

而两两比较算法的时间复杂度是O(M^2*N)

当前面M很大的时候，就很会影响性能，这也是为什么百度网盘或者各类存储系统中使用hash来作为比对的原因所在。