专栏首页AI机器学习与深度学习算法数据结构与算法 1-7 Python列表与字典操作的时间复杂度

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

本系列是我在学习《基于Python的数据结构》时候的笔记。本小节主要介绍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中的每一个元素;

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

本文分享自微信公众号 - AI机器学习与深度学习算法(AI-KangChen),作者:Chenkc

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-08-12

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数据结构与算法 1-6 Python列表类型不同操作的时间效率

    本系列是我在学习《基于Python的数据结构》时候的笔记。本小节首先回顾一下timeit代码执行时间测量模块,然后通过此模块测算Python中list列表一些操...

    Chenkc
  • 数据结构与算法 1-4 常见时间复杂度与大小关系

    本系列是我在学习《基于Python的数据结构》时候的笔记。本小节主要介绍一些常见的时间复杂度以及它们之间的大小关系。

    Chenkc
  • 机器学习入门 6-3 线性回归中的梯度下降法

    本系列是《玩转机器学习教程》一个整理的视频笔记。本小节主要介绍在线性回归中使用梯度下降法。

    Chenkc
  • 【NLP基础】NLP关键字提取技术之LDA算法原理与实践

    人们是如何从大量文本资料中便捷得浏览和获取信息?答案你肯定会说通过关键字。仔细想想,我们人类是怎么提取关键词?我们从小就接触语言,语法,当听到或者看到一句话时,...

    zenRRan
  • Python之从列表推导到zip()函数的五种技巧

    这 5几种方法,也许在入门阶段时,我们还不太了解它们,但在实战中这 几个技巧非常实用。

    Python知识大全
  • 学Python,从列表推导到zip()函数,这五种技巧应知应会

    在本文中,作者介绍了 5 种方法,也许在入门阶段时,我们还不太了解它们,但在实战中这 5 个技巧非常实用。

    CDA数据分析师
  • 学Python,从列表推导到zip()函数,这五种技巧应知应会

    机器之心已经介绍过很多 Python 教程,从非常齐备的长教程:一文掌握 Python 关键代码,到一些好玩的小技巧:Python 技巧 101,它们从不同的层...

    机器之心
  • 学Python,从列表推导到zip()函数,这五种技巧应知应会!

    最开始学 Python 时,如果我能掌握这些方法,那么代码看起来会更加优美。在本文中,作者介绍了 5 种方法,也许在入门阶段时,我们还不太了解它们,但在实战中这...

    1480
  • python模块--collection

    python的内建模块collections有几个关键的数据结构,平常在使用的时候,开发者可以直接调用,不需要自己重复制造轮子,这样可以提高开发效率。

    用户2398817
  • 本周新鲜事:开源那些事

    纯洁的微笑

扫码关注云+社区

领取腾讯云代金券

玩转腾讯云 有奖征文活动