String.indexOf()函数调用的成本/复杂性是多少?
据我所知,Java对 .indexOf()
的实现仅是“朴素字符串匹配算法”(naive string matching algorithm),它的平均时间复杂度为O(n+m)
,最坏情况下时间复杂度为O(n*m)
。
实际上,这已经足够快了。我测试了相对较大的目标字符串(>500个字符)和语料库(几MB),能在不到一秒钟内完成匹配(在普通家用计算机上)。请注意,我强制其遍历整个语料库。
O(n+m)
是平均情况?https://dev59.com/yGcs5IYBdhLWcg3wjUuR#12752295似乎与该观点相矛盾。 - Pacerier这取决于具体的实现。
例如,在搜索较长字符串中的子串时,“Turbo Boyer-Moore算法需要额外的常量空间来完成在2n次比较内的搜索(而不是Boyer-Moore的3n次),其中n是要搜索的文本中字符的数量。”(参见Wikipedia)。