代码之家 › 专栏 › 技术社区 › Jason

Java中的Strig.Cub()的Big-O是什么?

contains big-o string java

Jason · 技术社区 · 15 年前

我正在做一个项目,需要优化运行时间。是 String.contains() 运行时间与 TreeSet.contains() ,哪个是O(logn)?

我问的原因是我在建一个 TreeMap<String, TreeSet<Song>> ,其中歌曲包含一系列歌词。根据效率的不同,我正在考虑在歌曲中加入一组抒情词,并搜索这些词而不是字符串。

2 回复 | 直到 9 年前

NickL 9 年前

最著名的算法之一是 Boyer-Moore 字符串搜索算法是O(N),尽管它能在最佳情况下提供子行性能。

在Java中使用哪种算法取决于下载的实现方式。例如,openjdk似乎使用了一种简单的算法,在最佳情况下,它以O(NM)和线性性能运行。见第1770-1806行 here .

dty 15 年前

您也可以尝试使用TIE而不是TeaMeP(虽然Java没有内置的TIE实现)

推荐文章

Aidan · 为什么在将最后一个索引分配给空终止符(\0)后,我无法释放char缓冲区

1 年前

Ben · 统计向量中的单词在字符串中出现的频率

1 年前

Mehan Alavi · TCP Socket-打印字符串中所有不在C中的字符不起作用

1 年前

Haru Hoshizora · 为什么一个整数的位置没有改变,但值却不同

1 年前

bear_525 · 从列中删除中间名和首字母,并保存在单独的列中

1 年前

asdfadf · 为什么具有相同内存值的字符串和整数打印方式不同?

1 年前

DrakeMurdoch · 统计每行中的字符数,如果所有字符数都低于某个数字,则删除

1 年前

user764754 · 防止多行原始字符串文字中出现新行字符

1 年前

Bogaso · 从列表中返回与模式匹配的元素

1 年前

Jasco · 如何使用VBA提取两个相似字符之间的字符串中的单词?

1 年前