查找时间复杂度O(n)

文章/答案/技术大牛

发布

1回答

为什么我的质数代码不适用于大数，即使我使用了eratosthenes的筛子，我也使用了集合而不是列表？

python、python-3.x、set、sieve-of-eratosthenes

我的代码： import mathb=list(range(2,n+1)) for j in b: b[b.index(j)]=0 c={i for i in b if n%i==FalseUsers/r

浏览 19提问于2020-08-28得票数 1

1回答

使用isalnum()的loop语句的时间复杂度(Python)

python、time-complexity

时间复杂度是O(n^2)吗？我相信isalnum函数的时间复杂度是o(n)，因为它将遍历每个字符来检查它是否是字母数字，并且我们迭代n个单词。因为在for循环的每一次迭代中，我们做一个o(n)操作，这会使它变成O(n^2)吗？或者仅仅是2遍O(n)时间复杂度？

浏览 21提问于2021-09-04得票数 0

回答已采纳

1回答

python、time-complexity

考虑下面的代码： import matplotlib.pyplot as plt def pow(n): return 1x = pow(n//2) return x*xz = []

浏览 7提问于2019-04-24得票数 0

3回答

为什么Maps具有比Erlang中的记录更慢的查找属性？

erlang

映射通常实现为哈希表，因此查找时间复杂性为O(1)；记录(带有名称的元组)通常被实现为不可变列表，查找时间复杂度为O(N)。这些数据结构在Erlang中的实现有什么不同？

浏览 5提问于2015-09-20得票数 4

回答已采纳

3回答

它的时间和空间复杂性是O(n)。我相信solution2也有O(n)的空间复杂性。时间复杂度是多少？for循环是O(n)，但我不确定in语句，因为result的长度没有输入a那么长。它也只是O(n)吗最后，如果两个解决方案都有相同的时间和空间复杂性，其中一个被认为是“更好的”？我应该在面试中使用哪一种？看起来solution1使用了更多的空间(可能是O(2n)，但我知道我们应该去掉前面的常量)，

浏览 35提问于2020-09-23得票数 1

回答已采纳

1回答

搜索大排序文本文件的最快捷、最有效的方法

python、list、search、set、whoosh

我有一个大型的静态文本/csv文件，它包含大约100 k行(2MB)。它本质上是一个字典，我需要用Python对这些数据执行定期查找。 key value1 value2 alpha beta y1 y2 ... 这是一个web应用程序的一部分，每个用户都将一次查找100到300个键，

浏览 0提问于2019-04-03得票数 2

3回答

std::map的底层结构是什么？

c++、algorithm、optimization、hashmap

这对我来说没有意义，因为如果是这样的话，就不能检索O(1)。有人能解释吗？另外，如果要在不使用stdlib的情况下在C++中实现哈希表，那么最好的方法是什么？

浏览 10提问于2017-02-16得票数 0

回答已采纳

1回答

在Python中从dict中弹出一个元素的时间复杂度是多少？

python、algorithm、dictionary

do_something_if_key_not_present() do_something_if_key_is_present()for key in all_possible**的时间复杂度是什么?我知道在像list这样的结

浏览 0提问于2017-05-16得票数 10

回答已采纳

3回答

迭代字典的时间是恒定的吗？(因为查找是常量？)

python、dictionary、time-complexity、big-o

我的问题是关于字典的常数O(1)查找时间。我真正的问题是，总的时间复杂度是O(N^2)吗？

浏览 1提问于2021-08-14得票数 0

回答已采纳

3回答

哪种数据结构可以最大限度地减少哈希表存储桶中的查找成本？

algorithm、data-structures、hashmap、hashtable、time-complexity

给定具有冲突的哈希表，通用哈希表实现将导致桶中的查找在O(n)内运行，假设使用了链表。如果我们将链表转换为二叉树，我们将下降到O(log )。对存储桶本身使用哈希表将使查找时间减少到O(1)，但这需要对哈希函数进行巧妙的修改。

浏览 0提问于2012-08-09得票数 0

1回答

我应该用字典来测试成员资格吗？

python、python-3.x、time-complexity

我之所以这样问，是因为我觉得字典有最坏的查找时间O(1)，而对于数组则是O(n)。 if i in A_dict: else:如果我上面提到的时间复杂性是正确的，那么第一段代码的复杂度为O(x-x-)，而第二种代码的复杂度为O这是正确的吗？

浏览 0提问于2020-02-28得票数 3

回答已采纳

3回答

为什么把一个列表转换成一个集合比仅仅使用list来计算一个列表差更快呢？

python、performance、list、python-2.7、set

在中给出了一些性能基准更新:我知道一个集合的平均O(1)查找时间比列表的O(n)要长，但是如果最初的list A包含大约一百万个整数，那么创建集合不是需要更长的时间吗？

浏览 2提问于2014-08-13得票数 13

回答已采纳

2回答

创建列表时检查列表中值的复杂性

python、algorithm、time-complexity、complexity-theory

以下代码的最坏情况时间复杂度是什么？(2, "two"), (3, "three")] print("5 is not here") 我的理解是，它是O(n^2)，因为在搜索这个列表时，两人都在构建一个列表，所以等价于另一个for循环中的for循环。

浏览 1提问于2019-12-12得票数 0

回答已采纳

1回答

整数列表和整数集在时间效率上的差异

python、python-3.x

约束：n,m in range(10^5)，arr中的任意整数都在range(10^9)中请解释。n, m = input().split()A = set(map(int,input().split())) #list(map

浏览 0提问于2017-12-19得票数 1

1回答

大O表示法-用HashSet查找循环的正确定义

.net、big-o、computer-science

据我理解，简单的for循环将具有O(n)的复杂性。 // ...如果我在前面引入哈希查找，这会使复杂度保持在O(n)吗？record in records) {} 同样地，如果HashSet是一个列表，那么它的复杂性会变成O(n^2)吗？

浏览 1提问于2017-04-27得票数 2

回答已采纳

5回答

HashSet<T>(IEqualityComparer<T>)的查找时间复杂度是多少？

c#、runtime、complexity-theory、hashset

在C#.NET中，我喜欢使用HashSets，因为它们的查找时间复杂度假设为O(1)。如果要查询的数据集很大，我通常更喜欢使用HashSet而不是List，因为它具有这样的时间复杂性。让我感到困惑的是HashSet的构造函数，它将IEqualityComparer作为参数：在将元素添加到集合中时，实现是否会在内

浏览 7提问于2012-03-22得票数 26

回答已采纳

3回答