Python两种回溯算法实现的效率与内存布局有什么差异？

运行效率差异 #

• 第一种实现每次递归调用传递path + [x]时，都会触发一次列表拼接操作，该操作时间复杂度为O(k)（k为当前路径长度），且每一次递归都会执行一次拼接，总拷贝次数等于全部递归调用的次数，额外开销随路径长度、递归深度增长会快速放大。同时大量临时列表的创建、销毁也会带来额外的内存分配和垃圾回收开销。
• 第二种实现全程复用同一个路径列表，append()和pop()都是均摊*O(1)*的操作，仅在命中终止条件（找到合法路径）时才执行一次list(path)拷贝操作，总拷贝次数等于最终合法路径的数量，远低于第一种实现的拷贝次数，因此运行速度明显更快。

内存布局差异 #

• 第一种实现的每一层递归都持有独立的路径列表对象，递归深度为N时，同一时间内存中会存在N个不同长度的独立路径列表，占用多块离散的内存空间，内存利用率低，小对象过多也会加重Python垃圾回收器的负担。
• 第二种实现所有递归调用共享同一个路径列表的引用，内存中始终仅存在一份正在修改的路径对象，仅在存储结果时生成新的列表存入结果集，内存占用更低且布局更集中，垃圾回收压力极小。

补充说明 #

两种写法的逻辑正确性都是成立的：第一种因为每次传递的都是新生成的列表，终止条件处可以直接把引用加入结果集；第二种因为共享同一个列表，必须在终止条件处做一次拷贝，否则后续的pop()操作会修改已经存入结果集的路径内容，导致结果错误。

内容的提问来源于stack exchange，提问作者Alexey Abramov