Python3 list.count（）時間複雜度

Question

我一直在尋找關於此的文檔很多麻煩。 Python 3中list.count（）的時間複雜度是多少？我一直假設它只是O（n），有誰知道這是否是這種情況？

Answer 1

您可以使用timeit模塊嘗試一點實驗。

定時list.count(0)在大範圍的列表長度（10**0到10**6）。

from timeit import timeit 
from math import log10 
import matplotlib.pyplot as plt 

data = [] 
for i in [10**x for x in range(6)]: 
    data.append((i, timeit.timeit('x.count(0)', setup='x=list(range(%d))' % i, number=1000))) 

以時間和列表長度的日誌以便更好地觀察（注意，我們使用的是log10這裏，匹配列表長度的範圍）。

log_data = [log10(x), log10(y) for (x,y) in data] 

生成一個快速繪圖。

plt.figure() 
plt.scatter(*zip(*log_times)) 
plt.xlabel('log(n)') 
plt.ylabel('log(time)') 
plt.savefig('count_complexity') 

看來，這的確是O（n）的複雜性。