“就地”究竟是什么意思？

Question

我知道关于“就地”算法的含义还有其他问题，但我的问题有点不同。我知道这意味着算法会更改原始输入数据，而不是为输出分配新空间。但我不确定的是辅助记忆是否重要。即：

• 如果算法分配一些额外的内存来计算结果
• 如果一个算法有非常多的递归调用，占用了堆栈上的额外空间

Answer 1

我想不出任何不需要额外内存的就地算法。算法是否“就地”具有以下特征：

\n\n

\n

in-place：通过将输入变异为输出，使用 o(f(n)) 额外空间对大小为 \xce\x98(f(n)) 的输入执行算法。

\n

\n\n

以“插入排序”排序算法的就地实现为例。输入是占用 \xce\x98(n) 空间的数字列表。最坏情况下运行需要 \xce\x98(n ^{2 ) 时间，但只占用 O(1) 空间。}如果您不进行就地排序，则需要至少使用 \xce\xa9(n) 空间，因为输出需要是 n 个数字的列表。

\n