Python的deepcopy()的运行时复杂度是多少？
我正在尝试提高一个算法的速度，查看了哪些操作被调用后，我发现很难确定到底是什么导致了速度变慢。我在想，Python的deepcopy()函数是否可能是问题的根源，还是我应该更深入地检查一下自己的代码。
4 个回答
deepcopy()的复杂度取决于你要复制的对象的大小，也就是里面有多少个元素或子对象。
如果你的算法输入不会影响被复制对象的大小，那么在计算复杂度时，可以把调用deepcopy()看作是O(1)，因为每次调用的执行时间基本上是固定的。
（如果你的算法输入会影响被复制对象的大小，那你就需要详细说明一下是怎么影响的。这样才能评估算法的复杂度。）
你在用 deepcopy 做什么呢？顾名思义，deepcopy 是用来复制对象的，它会把对象和所有的子对象都一层一层地复制过去，所以这个过程所花的时间和你要复制的对象大小是成正比的。（还要花点时间处理循环引用的问题）
其实没有什么办法能让这个过程变快，如果你要复制所有的内容，那就必须把所有的内容都复制一遍。
你可以考虑问自己一个问题：你真的需要复制所有的东西吗？还是说你只需要复制结构中的一部分就可以了。
看看这段代码（你也可以看看），它会遍历所有被引用的对象树中的每一个对象（比如字典的键和值、对象的成员变量等），并对它们做两件事：
- 检查这个对象是否已经被复制过，通过在一个以对象ID为索引的
memo字典中查找 - 如果没有被复制，就进行复制
对于简单对象来说，第二步的操作是 O(1)，也就是很快。对于复杂对象，使用同样的方式处理，所以在整个树中，n 个对象的处理时间是 O(n)。第一步，在字典中查找一个对象的时间，平均来说是 O(1)，但在最坏情况下是 O(n)。
所以在最好的情况下，平均来说，deepcopy 的时间复杂度是线性的。memo 中使用的键是 id() 值，也就是内存地址，所以这些键在空间中并不是随机分布的（上面提到的“平均”部分），可能会表现得更差，最坏情况下达到 O(n^2)。我在实际使用中确实观察到了一些性能下降，但大多数情况下，它的表现是线性的。
这就是复杂度的部分，但常数项很大，deepcopy 绝对不便宜，可能会导致你遇到的问题。唯一确定的方法是使用性能分析工具——一定要去做。顺便说一下，我目前正在重写一段非常慢的代码，这段代码有 98% 的执行时间都花在了 deepcopy 上。