分析对比一下这几种数据结构查找的时间复杂度,原因是最近面试了几个人,有些开发经验,但是都没有回答的很好。

这里写一段代码对比一下:

In [1]: l = list(range(100000))

In [2]: s = set(range(100000))

In [3]: d = dict(zip(range(100000), range(100000)))

In [4]: %timeit 99999 in l
1.06 ms ± 9.94 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

In [5]: %timeit 99999 in s
46.4 ns ± 0.255 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

In [6]: %timeit d.get(99999)
115 ns ± 0.937 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

1ms = 1000000ns,可以看出,列表和集合字典的查找时间绝对不在一个量级上,特别是在数据量很大的情况下。由于在 Python 中 setdict 都是通过 hash 的方式实现的,所以查找的时间复杂度是 O(1),而字典的时间复杂度则是 O(n)。

发表评论

电子邮件地址不会被公开。 必填项已用*标注