合并两个deque的最优时间复杂度方案及相关技术问题咨询

初始代码：

from collections import deque

dq1 = deque([...])  # 长度为n
dq2 = deque([...])  # 长度为m

需求：将dq2按从左到右的顺序左扩展至dq1，最终保留dq1。

问题1：最优解决方案是否取决于n和m的大小？ #

是的，最优方案确实和n、m的大小相关。

• 当n > m时，直接在dq1上执行m次appendleft操作（总时间复杂度O(m)）更高效，无需额外创建或转移大对象引用。
• 当n < m时，将dq1扩展到dq2（时间复杂度O(n)）再让dq1指向dq2（O(1)）的成本更低，因为O(n)远小于O(m)。

问题2：指定代码行dq1 = dq2的时间复杂度是O(1)还是O(n+m)？ #

是O(1)。这行代码只是修改变量dq1的引用指向，让它和dq2指向同一个deque对象，没有复制任何元素，属于常数级时间开销。

问题3：是否存在比上述两种场景方案更优的解决方案？ #

从时间复杂度角度，你提出的分场景方案已经是最优的——它总能达到O(min(n,m))的时间复杂度，这是理论上的最优下限（至少需要处理min(n,m)个元素）。不过场景1的代码可以简化：

dq1.extendleft(reversed(dq2))

这行代码和你写的循环appendleft效果完全一致，时间复杂度同样是O(m)，但代码更简洁。

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