0%

一、Python 程序的计算代价

O(1) 称为常量复杂度,O(log n) 称为对数复杂度,O(n) 称为线性复杂度,O(n²) 称为平方复杂度,O(2ⁿ) 称为指数复杂度。

  • 基本算术运算是常量时间操作,逻辑运算是常量时间运算。
  • 组合对象有些是常量时间,有些不是。
    • 复制和切片通常需要线性时间(与长度有关,是 O(n) 时间操作)。
    • list 的元素访问和元素赋值(以及 tuple 的元素访问),是常量时间
    • dict 情况比较复杂。
  • 字符串也应该看做组合对象,许多操作不是常量时间。
  • 创建对象也需要时间和空间,所需的大小与对象的规模有关,通常应该看做线性时间和线性空间操作。
  • 构造新的的 list、set 结构,构造空结构(空表、空集合)是常量时间操作,而构造一个包含n个元素的结构,则至少需要 O(n) 时间。
  • 一些 list 操作的效率:元素访问和元素修改是常量时间操作,一般的加入/删除元素操作(即使只加入一个元素)都是 O(n) 时间操作,在表的最后加入和删除元素的操作效率高,在其他地方加入和删除元素的操作效率低。
  • 字典操作效率,加入新的键值对,最坏的情况复杂度是 O(n),但平均复杂度是 O(1)。
  • Python 的各种组合数据对象都没有预设的最大元素个数,从空间占用的角度看,其实际开销在存续期间可能变大,但通常不会缩小(即使后来元素变得很少了),比如删除元素。
  • 如果在程序中建立了一个表,此后一直将其作为全局变量的值,这个对象就会始终存在并占用存储空间。如果将其作为某个函数里局部变量的值,或者虽然作为全局变量的值,但是通过复制将其抛弃,这个对象就可以被回收。