转自：https://blog.csdn.net/siyue0211/article/details/
列表和元组
列表和元组的区别是显然的：列表是动态的，其大小可以该标；而元组是不可变的，一旦创建就不能修改。
实现细节
python中的列表的英文名是list，因此很容易和其它语言(C++, Java等)标准库中常见的链表混淆。事实上CPython的列表根本不是列表（可能换成英文理解起来容易些：python中的list不是list）。在CPython中，列表被实现为长度可变的数组。
从细节上看，Python中的列表是由对其它对象的引用组成的连续数组。指向这个数组的指针及其长度被保存在一个列表头结构中。这意味着，每次添加或删除一个元素时，由引用组成的数组需要该标大小（重新分配）。幸运的是，Python在创建这些数组时采用了指数过分配，所以并不是每次操作都需要改变数组的大小。但是，也因为这个原因添加或取出元素的平摊复杂度较低。
不幸的是，在普通链表上“代价很小”的其它一些操作在Python中计算复杂度相对过高。
- 利用 list.insert方法在任意位置插入一个元素——复杂度O(N)
- 利用 list.delete或del删除一个元素——复杂度O(N)
| 操作 | 复杂度 |
|---|---|
| 复制 | O(N) |
| 添加元素(在尾部添加) | O(1) |
| 插入元素(在指定位置插入) | O(N) |
| 获取元素 | O(1) |
| 修改元素 | O(1) |
| 删除元素 | O(N) |
| 遍历 | O(N) |
| 获取长度为k的切片 | O(k) |
| 删除切片 | O(N) |
| 列表扩展 | O(k) |
| 测试是否在列表中 | O(N) |
| min()/max() | O(n) |
| 获取列表长度 | O(1) |
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/22396.html