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）の複雑さであるようです。