关于list和set 中 contains()方法 实现度效率的问题、O(1)和O(n)等。。。

Question

Set的    contains()方法    实现的复杂度是O(1)、

List的    contains()方法    实现的复杂度是O(n)

List特点：元素有放入顺序，元素可重复 ，

Set特点：元素无放入顺序，元素不可重复（注意：元素虽然无放入顺序，但是元素在set中的位置是有该元素的HashCode决定的，其位置其实是固定的） 

附上二者contains()方法的区别对比：

1、HashSet的contains返回true，当且仅当equals返回true    并且    hashCode返回相等的值 ；Set除了比较equals，还比较hashCode

2、list.contains(o)，系统会对list中的每个元素e调用o.equals(e)，方法，加入list中有n个元素，那么会调用n次o.equals(e)，只要有一次o.equals(e)返回了true，那么list.contains(o)返回true

算法时间复杂度的表示法O(n²)、O(n)、O(1)、O(nlogn)

简单理解： 就是变量为n的时候，算法需要对变量操作次数的量级。

简单解释：

   简单说O(n²)表示当n很大的时候，复杂度约等于Cn²，C是某个常数，简单说就是当n足够大的时候，n的线性增长，复杂度将沿平方增长。

   O(n)也是差不多的意思，也就是说n很大的时候复杂度约等于Cn，C是某个常数。

   O(1)就是说n很大的时候，复杂度基本就不增长了，基本就是个常量C。

详细可以看《算法》第四版

Answer 1

Geely 2017-08-17 22:55:22

哈哈哈哈哈不扶墙！就服你！！！

• 提问者 Mr温少 #1

  哈哈ヾﾉ≧∀≦)o    就为了弄清这个知识点，查资料，我还学了好多东西，感觉老师太牛了……随便一句话，我得个把小时才能消化，报道出家  底子还是太薄啊

Answer 2

提问者 Mr温少 2017-08-17 21:36:26

额，因为自己犯了一个低级错误，感觉有点小丢人，又不能删除，就把问题改为了知识点，就放了一点自己查的知识点，哈哈哈哈~~