知识卡片
列表操作按工作量比较
列表复制、遍历和成员查找通常随元素数n增长;长度与索引访问通常常数级,取长度k的切片还需复制k个引用。extend与重复构造则取决于新增或生成的规模。表中复杂度是相应实现和通常操作的成本模型,用户对象比较可另有成本;切片复制是浅复制,不等于连同元素对象一起复制。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第2章 语法最佳实践——类级别以下 2.1.2 集合类型 · 查看原书依据
获取长度为k的切片 O(k)
参考来源
- 位置:《Python编程精进(第1辑)(套装共3册)(异步图书)》Python高级编程(第2版) · 第2章 语法最佳实践——类级别以下,spine011单元004;来源项目book-sources,extracted/Python编程精进(第1辑)(套装共3册)(异步图书)/_epub-src/OEBPS/text00010.html。
- 结论依据:原文复杂度表将长度k切片列为O(k),与索引和遍历分开,支持按复制或访问的引用数量解释成本而非看方法名。未在本机运行示例或改变环境。
- 原始内容:) 删除元素 O(n) 遍历 O(n) 获取长度为k的切片 O(k) 删除切片 O(n) 修改长度为k的切片 O(k+n) 列表扩展(Extend) O(k) 乘以k O(nk) 测试元素是否在列表中(element in list) O