Python3中的list、set和dict

你真的了解python中的列表,元组和字典吗?

先来回答一下几个问题:

  1. python中求list长度的len方法的时间复杂度是多少?
  2. python中list中的in操作符,时间复杂度是多少?
  3. python中set中的in操作符,时间复杂度是多少?
  4. python中dict中的in操作符,时间复杂度又是多少?为什么?

列表

我们先来看list相关内容,list我们很常见也很熟悉,list是python的内置类型,在cpython中是通过c语言来实现的。对于len取长度的操作,其时间复杂度是O(1)。对于大多数python中的len操作来说,其时间复杂度通常都是O(1)。其实现中是设置了一个常量用于记录数组的长度,因此取长度的操作是O(1).

对于list的in操作来说,需要遍历一次,因此其时间复杂度为O(n)。

集合

我们知道,集合的特性是无序,元素唯一不重复。集合的实现跟字典类型,可以看作是只有key没有value的字典,因此其底层也可以看作是哈希的实现,所以,对于集合的in操作,其时间复杂度为O(1),而不是O(n)。

字典

字典就是哈希表的实现了,我们知道字典的查找其时间复杂度是O(1)。但是在python2中,dict.keys()返回的是一个列表,对列表的in操作,前边已经说过,是O(n),因此,在python2中,key in dict.keys()的操作是要慢于key in dict的。在python3中,dict.keys()返回的是一个dict_keys对象,dict.values返回的是一个dict_values对象,dict.items返回的是一个dict_items对象,python3中的in操作并没有什么优化,仅仅是从hash表中查找而已。