我刚刚查看了 Java String
类的 .indexOf()
方法的实现,代码的作者似乎使用了蛮力算法来找到给定字符串中的子字符串。也就是说,该方法的运行时间复杂度为 O(mn),其中 m 和 n 分别是源字符串和目标字符串的长度。
为什么作者不使用更高效的算法,如 Rabin-Karp,如果提供良好的哈希函数,其运行时复杂度为 O(m + n)?
我可能遗漏了此实现原因背后的完整知识,因此想了解。
最佳答案
我不确定为什么会做出这个决定,但如果我猜的话,这可能是因为对于小模式字符串(一个非常常见的用例),天真的暴力算法可能和一些算法一样快,如果不是更快的话渐进更快的算法,如 Rabin-Karp、Boyer-Moore 或 Knuth-Morris-Pratt。这似乎是一种合理的默认算法,因为在许多情况下,您将在小字符串中搜索小模式,强大的匹配设置的开销可能与朴素方法的运行时间相当。
也就是说,Java 规范中没有任何地方强制要求使用这种算法。他们可以很容易地选择 Rabin-Karp 作为默认算法。
他们可能选择这种方法的另一个原因是,如果您想进行快速文本搜索,正则表达式库提供了更快的字符串匹配和更强大的搜索功能。默认情况下为用户提供简单的蛮力算法,并在需要时选择切换到更强大的工具集,这似乎是平衡渐近效率与实际效率的好方法。
关于java - Java中.indexOf方法的算法选择,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4997170/