Python3 list.count() 시간 복잡성

Question

나는 이것에 관한 문서를 찾는 데 많은 어려움을 겪고 있습니다. 파이썬 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)의 복잡도 실제로 것 같다.