“就地”究竟意味着什么？

我知道还有其他关于“就地”算法的含义的问题，但我的问题有点不同。我知道这意味着算法会改变原始输入数据，而不是为输出分配新的空间。但是我不确定的是辅助内存是否计数。即：“就地”究竟意味着什么？

2014-10-10 NPS

哪里有上帝的名字，我问任何“书籍，工具等......”？ – NPS 2014-10-10 01:48:13

我想知道同样的事情。由于另一个原因，我可能会看到该问题可能会被关闭，但这不会提出异地资源请求。 – 2014-10-10 05:41:55

我认为这是一个非常好的问题 - 绝对不是推荐问题 - 但我不能投票重新打开它，对不起。你可能会考虑在聊天中提问。 – 2014-10-11 02:29:03

我想不出任何就地算法，不需要一些额外的内存。是否算法被“就地”的特征在于以下内容：

就地：使用邻要在尺寸Θ的输入执行一个算法（F（N））（F（N））通过将输入变为输出来增加空间。

以“插入排序”排序算法的就地实现为例。输入是一个Θ（n）空格的数字列表。在最坏的情况下，需要运行Θ（n ）时间，但它只需要O（1）空间。如果你不在原地进行排序，那么所需的至少要使用Ω（n）空格，因为输出需要是n个数字的列表。

2014-10-10 00:23:43

就地通常意味着子线性附加空间。这不一定是该术语含义的一部分。只是使用线性或更大空间的就地算法并不令人感兴趣。如果您要分配O（n）空间来计算与输入相同空间的输出，您可以在新内存中同样轻松地生成输出并保持相同的内存限制。现场计算的价值已经丧失。

维基百科走得更远，并说the amount of extra storage is constant。然而，使用log（n）额外空间将输出写入输入的算法（比如mergesort）在我看过的用法中仍然是原地的。

2014-10-10 00:28:40 Gene

算法简介（CLRS）第148页：“回想一下，如果输入数组中只有恒定数量的元素存储在阵列外部，则排序算法会进行排序。”但在其他地方，它描述了递归快速排序，尽管它使用log n空间作为堆栈。 – 2014-10-10 00:32:14

@JeffreyBosboom对。维基百科的文章同样令人困惑和困惑。 – Gene 2014-10-10 00:35:38

回答