一个String.indexOf()函数调用的成本/复杂度是多少？

Question

String.indexOf()函数调用的成本/复杂性是多少？

- Jim

---

用什么语言，与什么进行比较？函数的参数是什么 - 它接受一个字符串、一个字符、一个自定义比较器吗？ - Kobi

你说的是Java吗？ - NullUserException

Java中的indexOf(String str)方法的复杂度是什么？ - Shayan_Aryan

Answer 1

据我所知，Java对 .indexOf（） 的实现仅是“朴素字符串匹配算法”(naive string matching algorithm)，它的平均时间复杂度为O(n+m) ，最坏情况下时间复杂度为O(n*m)。

实际上，这已经足够快了。我测试了相对较大的目标字符串（>500个字符）和语料库（几MB），能在不到一秒钟内完成匹配（在普通家用计算机上）。请注意，我强制其遍历整个语料库。

- NullUserException

---

我知道这是很久以前的事了，但你知道那是从哪里得到的吗？我需要那个信息来写我的学士论文，我不知道Stackoverflow是否可以作为论文的可接受参考。 ;) - odaa

@odaa 我在大学期间进行了一些实验并写了一篇论文。 - NullUserException

@NullUserException，你为什么说O(n+m)是平均情况？https://dev59.com/yGcs5IYBdhLWcg3wjUuR#12752295似乎与该观点相矛盾。 - Pacerier

@Pacerier 平均情况下为O(n+m)，最坏情况下为O(n*m)。 - NullUserException

@NullUserException 如果您能展示一下您的基准测试结果，那就太好了。 - heroin

Answer 2

在Java中，如果调用的是string1.indexOf(string2)，时间成本将为O(m-n)，其中m是string1的长度，n是string2的长度。

- MEURSAULT

Answer 3

这取决于具体的实现。

例如，在搜索较长字符串中的子串时，“Turbo Boyer-Moore算法需要额外的常量空间来完成在2n次比较内的搜索（而不是Boyer-Moore的3n次），其中n是要搜索的文本中字符的数量。”（参见Wikipedia）。

- jm.

---

@caleb：真的吗，你怎么从问题中看出来的？ - jm.