数据结构与算法 1-7 Python列表与字典操作的时间复杂度

一

list内置操作的时间复杂度

接下来简单说明几个重要的list内置操作的时间复杂度：

1. index[]索引可以获取list中相应索引位置的元素，时间复杂度为O(1)，表明通过一步操作就能够定位到索引的元素，而不是遍历所有元素，这也是Python中list结构的特点：允许对元素进行快速的随机访问（即检索位于特定索引位置的元素）；
2. appen在list尾部追加元素，时间复杂度为O(1)，同样只需要一步就能在list尾部追加元素；
3. pop()移除list列表中的最后一个元素，并返回该元素的值，时间复杂度为O(1)，表明只需要一步操作即可完成移除最后一个元素的操作；
4. pop(i)移除list中指定位置的元素，并返回该元素的值，时间复杂度为O(n)，如果将i设置为n（list列表元素的个数），相当于pop()移除list列表最后一个元素，此时时间复杂度应该是O(1)而不是O(n)。这是因为我们通常说的时间复杂度指的是最坏时间复杂度，也就是最坏的情况下需要执行n个步骤才能完成移除list中指定位置的元素；
5. del operator删除list，时间复杂度为O(n)，表示将list中的元素一个一个的清空；
6. iteration迭代list元素，时间复杂度为O(n)，也就是遍历list列表中的每一个元素；
7. contains(in)使用in操作符判断元素是否在list列表当中，时间复杂度为O(n)，需要遍历一遍list列表才能知道；
8. get slice[x: y]取切片擦偶作，从x位置开始取到第y-1个位置，时间复杂度为O(k)，此时的k就代表从x到y-1位置元素的个数，首先定位到x位置，由前面index操作时间复杂度可以知道定位x位置的操作时间复杂度为O(1)，定位完以后需要一取元素，取多少个元素由x到y-1之间元素个数k所决定。此时和list中元素总数n没有关系，100个元素取1:6只取5个元素，从10000个元素中取1:6也是取5个元素，因此时间复杂度和n没有关系，只与切片元素的个数有关；
9. del slice删除指定切片的操作，时间复杂度为O(n)，如果将list中间几个位置的元素删除，删除的位置就为空，空的话后面的元素就会向前移动，把空的位置补上。通常时间复杂度指的是最坏时间复杂度，因此最坏的情况就是删除list列表最前面的元素，然后后面的所有元素都要向前移动，因此总体的时间复杂度仍然是O(n)；
10. set slice设置切片操作，时间复杂度为O(n + k)，set slice操作可以分为两个步骤：
    1. 先把需要把切片的元素删除掉，就是del slice操作，这个时候时间复杂度为O(n)；
    2. 然后把需要设置的切片元素补充上，补充的切片有k个元素，时间复杂度为O(k)；
    3. 所以set slice设置切片操作的时间复杂度为O(n + k)；
11. reverse逆序列表操作，需要将每一个元素逆置，所以时间复杂度为O(n)；
12. concatenate操作还讲连个list列表拼接在一起，时间复杂度为O(k)，把第二个list列表中的元素补充到第一个list列表中，此时的k是第二个列表中元素的个数，往队尾添加一个元素的时间复杂度为O(k)，因此将第二个列表中的k个元素添加列表尾部的操作时间复杂度为O(k)；
13. sort是对列表中的元素进行排序，此时的时间复杂度为O(nlog n)，当然这和list封装使用的排序算法有关；
14. nultiply列表相乘的操作，时间复杂度为O(nk)，n为列表中元素的个数，而k为需要相乘的次数。比如li = [1, 2, 3] * 10，此时对应的n = 3，k = 10；

需要记住下面几个内置操作：

1. index索引的时间复杂度为O(1)；
2. append队尾添加元素的操作时间复杂度为O(1)；
3. pop(i)指定位置删除元素并返回元素，时间复杂度为O(n)；
4. insert(i, item)指定位置插入元素，最坏情况下在第一个位置插入元素，相应的最坏的时间复杂度为O(n)；
5. contains(in)使用in操作符判断元素是否在list列表当中，时间复杂度为O(n)，需要遍历一遍list列表才能知道；

二

dict内置操作的时间复杂度

1. copy操作时间复杂度为O(n)，把字典中的所有元素都生成一份；
2. get item操作获取字典中的值，时间复杂度为O(1)，字典是拥有键值对的结构，获取元素可以通过键来索引，执行一步就可以获取到键所对应的值；
3. set item设置字典中的值，时间复杂度为O(1)，通过字典中的键来索引设置对应的值；
4. delete item删除的字典中元素，时间复杂度为O(1)，同样是通过字典中的键来索引删除对应的值；
5. contains(in)看dict中是否有指定的元素，时间复杂度为O(1)，使用字典可以不用进行遍历，字典中维护着一个键，所以他能一步找到看对应元素是否在dict中；
6. iteration迭代dict操作，时间复杂度为O(n)，因为dict是一个可迭代对象，因此可以通过for循环进行迭达，迭达操作需要遍历dict中的每一个元素；

总的来说，对于不同数据类型，相应的内置操作可能有不同的时间复杂度。