Java 中 String.contains（）的 Big-O 是什么？

string contains java big-o

2022-09-01 06:10:34

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

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

答案 1

最著名的算法之一是Boyer-Moore字符串搜索算法，它是O（n），尽管它可以在最佳情况下提供子线性性能。

Java 中使用哪种算法取决于您下载的实现。例如，OpenJDK似乎使用了一种天真的算法，该算法在O（nm）中运行，并且在最佳情况下以线性性能运行。请在此处查看第 1770-1806 行。

答案 2

.contains()绝对使用幼稚的方法，相当于时间的复杂性。O(nm)

在与模式匹配相关的问题之一中，我使用了，并且它花了，而用替换该行将时间减少到..contains()70 mspatternSearch() //KMP search14 ms

Java 中 String.contains（） 的 Big-O 是什么？