stepanevgen2013 Asked:2022-04-05 22:59:51 +0000 UTC2022-04-05 22:59:51 +0000 UTC 2022-04-05 22:59:51 +0000 UTC 为什么检查集合和列表中是否存在元素需要不同的时间？ 772 为什么检查集合和列表中是否存在元素需要不同的时间？ python 2 个回答 Voted Zhihar 2022-04-05T23:13:16Z2022-04-05T23:13:16Z 因为在列表（数组）中，要检查元素是否存在，您需要查看所有 (!!!) 元素，即 花费 O(n) 时间（线性时间） 而在集合中，为了了解存储元素的元素的索引，可以从元素计算hash index = hash(value) 在这种情况下，对元素的搜索将花费固定时间 O(1) Best Answer CrazyElf 2022-04-06T03:06:49Z2022-04-06T03:06:49Z 在集合中，就像在字典中一样，检查是通过元素的哈希（字典的键）执行的，它巧妙地转换为内存中元素的地址。如果发生冲突并且不同元素具有相同的散列，则有一种解决冲突的机制。在最简单的情况下，这是一个具有相同哈希的元素列表，在其中继续搜索。一般来说，在少量冲突的情况下，在集合和字典中按键搜索具有 O(1) 复杂度。 但是在列表中搜索时，您需要依次遍历其元素，直到找到所需的元素，这是 O (n) 复杂度。
因为在列表（数组）中，要检查元素是否存在，您需要查看所有 (!!!) 元素，即 花费 O(n) 时间（线性时间）
而在集合中，为了了解存储元素的元素的索引，可以从元素计算hash
在这种情况下，对元素的搜索将花费固定时间 O(1)
在集合中，就像在字典中一样，检查是通过元素的哈希（字典的键）执行的，它巧妙地转换为内存中元素的地址。如果发生冲突并且不同元素具有相同的散列，则有一种解决冲突的机制。在最简单的情况下，这是一个具有相同哈希的元素列表，在其中继续搜索。一般来说，在少量冲突的情况下，在集合和字典中按键搜索具有 O(1) 复杂度。
但是在列表中搜索时，您需要依次遍历其元素，直到找到所需的元素，这是 O (n) 复杂度。