在Java中，String()的Big-O是什么？

我正在处理一个项目，需要优化运行时间。String.contains()运行时是否与TreeSet.contains()相同，即O(LogN)？

我问这个问题的原因是我正在构建一个TreeMap<String, TreeSet<Song>>，其中的歌曲包含一串歌词。根据效率的不同，我正在考虑在歌曲中包含一组歌词，并对其运行搜索，而不是对字符串进行搜索。

---

解决方案

最著名的算法之一是Boyer-Moore字符串搜索算法，虽然它在最好的情况下可以提供次线性性能。

在Java中使用哪种算法取决于您下载的实现。例如，OpenJDK似乎使用了一种运行在O(Nm)内的朴素算法，在最好的情况下，它的性能是线性的。参见行1770-1806here。