跨迭代的辅助空间复杂度

Question

假设我们有以下函数：

def ReverseStr(s, k):
    """
    s: list of characters (length n)
    k: integer
    """
    for i in range(0, len(s), 2*k):
        s = s[:i] + s[i:i+k][::-1] + s[i+k:]
    return s

在此函数中，每次迭代都涉及创建四个不同的子列表。首先，我们创建一个长度为

i

的子列表。然后，我们创建一个大小为

k

的子列表；当我们反转这个大小为

k

的子列表时，我们创建了另一个大小为

k

的子列表。最后，我们创建一个大小为

n - (i + k)

的子列表。因此，总的来说，我们创建的子列表的总空间为

i + k + k + n - (i + k)

，或者简化为

n + k

。

空间复杂度定义为函数在任何给定点占用的最大空间量。虽然这个定义对我来说很有意义，但我很难理解连续迭代中会发生什么。例如，假设我们正在进行第四次迭代。在第一次、第二次和第三次迭代中创建的子列表是否仍然存储在内存中的某个位置？如果是这样，那么我们的空间复杂度分析必须考虑连续迭代中的内存积累。如果不是，那么我们就知道任何给定点消耗的最大空间发生在单次任意迭代期间；

O(n+k)

。

Answer 1

每次迭代都涉及创建四个不同的子列表。

事实上，还有通过执行

+

运算符创建的列表（列表串联）

因此，我们总共创建了总空间为 i + k + k + n - (i + k) 或简化为 n + k 的子列表。

在确定辅助空间复杂性时，通常的做法是丢弃可以进行垃圾收集的内存，即使实际上垃圾收集器可能不会立即释放内存。

我们从

s

的记忆开始，它有

n

元素。但这不属于辅助空间，所以我们可以丢弃它。

那么执行顺序是这样的：

 s[:i]

这为长度的列表分配内存

i

 s[i:i+k]

这为长度的列表分配内存

k

...[::-1]

这会为另一个长度为

k

的列表分配内存，但原始列表（上一步的）不再被引用，因此可以被垃圾收集。因此，我们可以得出结论，这是一个收支平衡的操作，不会增加引用对象使用的内存。

... + ...

前两项连接起来，创建一个长度为

i + k

的列表。但在这里，不再引用此串联的操作数，因此就内存而言，这相当是一种收支平衡操作（忽略列表的开销 - 我们从两个列表变为只有一个列表）。

s[i+k:]

这会为长度为

n - i - k

的列表分配内存。因此，我们现在的辅助内存总量为

n

—— 就这些列表引用的对象数量而言，再次忽略拥有 2 个活动列表的开销。

... + ...

这是第二个串联。操作数的内存将变为可垃圾回收，并且只有

n

元素的结果列表仍然可用。

最后对

s

的赋值开始，它处理

s

的原始值，将“活动”内存减少到

n

对象引用，可以说它们不再是“辅助”的，因为它们现在由

s

。

因此峰值位于辅助内存的

n

对象引用处，不包括最多 2 个列表的列表开销。

辅助内存复杂度因此为 O(𝑛)。

改善

您可以将辅助内存复杂度降低到 O(𝑘)，如下所示：

def ReverseStr(s, k):
    for i in range(0, len(s), 2*k):
        s[i:i+k] = s[i+k-1:i-1 if i else None:-1]
    return s

这里

s

被修改为就地。反向切片在一次操作中创建，需要 O(𝑘) 辅助内存，一旦分配完成，该辅助内存将再次被丢弃。