问哪一个更快？List.contains()或Map.containsKey()
EN

Stack Overflow用户

提问于 2012-07-23 21:21:40

回答 1查看 39K关注 0票数 31

我正在写一个算法，在这里我寻找成对的值，当这些值加在一起时，会产生另一个我正在寻找的值。

我计算出，使用Map可以将我的算法从O(n²)加速。后来我意识到我并没有真正使用Map中包含的值，所以List就足够了。

我在Google上做了一个强大的搜索，但在我的问题标题中没有找到任何关于这些方法的渐近运行时间的信息。

你能指出我应该在哪里找到这些信息吗？

发布于 2012-07-23 21:25:11

Map.containsKey()考虑到您使用的是HashMap，因为在HashMap中的搜索是在O(1)中完成的。

List.contains()通常应该采用顺序搜索或二分搜索，因此复杂度至少为O(log )

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/11613382

复制

相似问题

问哪一个更快？List.contains()或Map.containsKey()EN