Python3 list.count() временная сложность

Question

У меня возникли проблемы с поиском документации по этому вопросу. Какова временная сложность list.count() в Python 3? Я предполагал, что это просто 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') 

Похоже, что это на самом деле О (п) сложность.