如何归类该Python算法？In-place、严格In-place与O(1)空间辨析

算法代码 #

def foo(arr):
    # original_len = len(arr)
    tmp = []
    while arr:
        tmp.append(arr.pop())
    while tmp:
        arr.append(tmp.pop())

算法功能 #

这段代码的核心作用是反转输入的列表arr：先将原列表的元素从尾部弹出并放入临时列表tmp，再将tmp的元素弹出放回原列表，最终得到原列表的反转结果。

空间复杂度争议分析 #

抽象算法层面的O(1)说法 #

从算法设计的抽象逻辑来看，任意时刻len(arr) + len(tmp)都等于原数组的长度，仅额外创建了一个列表对象（tmp的结构本身是常量级开销），因此有人会认为该算法的空间复杂度是O(1)。但这种分析完全忽略了Python列表的底层实现细节。

Python列表实现的实际空间开销 #

Python列表本质是动态连续数组，其内存管理有两个关键特性：

1. 列表扩容时会预分配额外的连续内存块，不会刚好只分配当前元素所需的空间；
2. 列表缩容（比如pop()操作）时，底层的连续内存不会立即释放，只会调整列表的长度标记。

这意味着：当你把arr的元素逐步移到tmp时，arr的底层内存依然占据着原有的连续空间，而tmp会随着元素添加不断扩容，需要新的连续内存块。比如你提到的原数组占32个内存桶的场景，当移动第31个元素时，tmp可能需要分配新的内存桶，此时总内存占用会超过原数组的大小——实际空间复杂度是O(n)。

原地算法的界定 #

常规原地算法 vs 严格原地算法 #

• 常规意义上的"原地算法"指直接修改输入数据结构，不额外创建与输入规模同量级的独立数据结构。但这段代码创建了tmp，其最大长度等于原数组长度，因此不属于严格意义的原地算法。
• 严格原地算法要求额外辅助空间是常量级（O(1)），即辅助空间的大小与输入规模n无关。这段代码的tmp需要存储所有元素，属于O(n)的辅助空间，完全不符合严格原地的定义。

关于内存复用的疑问解答 #

1. 仅分配新列表就已经排除了严格原地的可能：严格原地不允许使用与输入规模同量级的辅助存储，创建tmp本身就违反了这个要求。
2. Python列表无法实现你假设的内存复用：动态列表的连续内存特性决定了，arr释放的内存块（即使实际空闲）无法被tmp复用——tmp的扩容是向高地址方向分配新的连续块，而arr的内存块依然占据原地址空间，两者无法重叠复用。

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