list.count()等内置方法的复杂性.它们需要O(1)时间吗

Question

我有两个方法来计算任何元素的出现次数。一种是使用内置的方法count，另一种使用循环。第二种方法的时间复杂度是O(n(，但不确定内置方法的时间复杂性
count占用的时间是O(1)还是O(n)
还请告诉我其他内置方法，如reverse、index等。

使用count。

List1 = [10,4,5,10,6,4,10]
print(List1.count(10))

使用循环

List2 = [10,4,5,10,6,4,10]
count = 0
for ele in List2:
if (ele == 10):
count += 1
print(count)

Answer 1

根据文件

list.count(x(-返回x在列表中出现的次数。

现在想想：如果你在一些彩色球上有10个杯子，在检查所有杯子之前，你能100%确定杯子下红色球的数量吗？

提示：无

因此，list.count(x)必须检查整个列表。由于列表的大小为n，所以list.count(x)必须是O(n)。

编辑：对于迂腐的读者来说，当然可以有一个存储每个项目计数的列表实现。这将导致存储器使用的增加，但将为list.count(x)提供O(1)。

编辑2：您可以在这里查看list.count的实现。您将看到正好运行n次的for循环，这肯定回答了您的问题：内置方法不一定需要O(1)时间，list.count(x)是内置方法O(n)的一个示例

Answer 2

python中的内置count()方法也具有O(n(的时间复杂性

对于具有n个元素的列表，count(value(方法的时间复杂度为O(n(。标准Python实现cPython"触摸"原始列表中的所有元素，以检查它们是否等于该值。因此，时间复杂性在列表元素的数量上是线性的。

Answer 3

这是一件很容易自己看到的事情。

>>> import timeit
>>> timeit.timeit('x.count(10)', 'x=list(range(100))', number=1000)
0.007884800899773836
>>> timeit.timeit('x.count(10)', 'x=list(range(1000))', number=1000)
0.03378760418854654
>>> timeit.timeit('x.count(10)', 'x=list(range(10000))', number=1000)
0.2234031839761883
>>> timeit.timeit('x.count(10)', 'x=list(range(100000))', number=1000)
2.1812812101561576

也许比O(n(好一点，但肯定比O(1(更接近。