当额外允许的空间为O(1)时，这意味着什么？

Question

如果一个编程问题给定了上述条件，而我使用递归解决它，那么我是否违反了约束条件？这可能是因为递归也使用堆栈？这样说对吗？

- Jainab Bano

---

从技术上讲，如果您拥有适当的尾调用优化，那么您可以对问题进行递归解决方案，该方案仅需要O(1)堆栈空间，与输入无关。递归基本上就是一个循环。例如，Scheme强制在所有符合规范的实现中消除尾调用... - Dirk

这就是为什么快速排序算法不是真正的原地算法（如果你所说的原地算法指的是 O(1) 的空间复杂度...）。 - Bakuriu

@Bakuriu 但是快速排序可以被编写成循环，并且可以使空间复杂度为O(1)，尽管它可能会在时间复杂度上失去优势。请参见https://dev59.com/62ox5IYBdhLWcg3wmFaV - a06e

Answer 1

如果递归的栈深度是常数并且不随输入大小而改变，则递归解决方案可以使用O(1)的额外空间。

一些编译器可能会进行尾调用优化（TCO），并删除递归调用，如果它们是通过函数执行的任何给定代码路径中的最后一个语句。使用TCO，没有调用堆栈相关的内存开销。

然而，请记住，O(1)约束可能是被强制施加的，以迫使您选择特定（可能是非递归）算法，因此即使您知道您正在使用的编译器已对您的代码进行了相关转换，依赖于尾调用优化可能是不明智的。至少，如果您依赖它，您应该明确说明并通过参考语言规范、编译器文档和/或适当的反汇编来证明您希望进行TCO的期望。

- perreal

---

那是一种不寻常的递归，通常随着输入的增加而变得更深。 - Thilo

一个例子是基于运算符优先级的解析器，其中parse(9)调用parse(8)，parse(8)调用parse(7)，依此类推，直到每个运算符的优先级都被处理完毕。 - user743382

如果游戏中可行的移动总数有限，那么用于搜索算法的调用次数可能是固定的。 - perreal

@delnan，这是我在生产代码中真正看到使用的东西。至于perreal的例子，如果一个游戏总是准确地（例如）向前看四步，那么仍然可以使用固定深度递归来实现。 - user743382

对于支持尾调用消除的语言，尾递归也可以避免使用堆栈空间。 - Tarik

Answer 2

extra allowed space is O(1)

意思是你的程序只能使用固定量的空间，例如 C。

根据大O符号的定义，这意味着你的程序所需的空间不能取决于输入的大小，尽管 C 可以任意大。

因此，如果递归依赖于输入的 ^a（通常是这种情况），那么你的程序所需的空间就不是 O(1)。

进一步澄清：

• 一个每次总是使用 1 Mb 的程序使用 O(1) 空间。

• 一个总是使用 1 Tb 的程序也使用 O(1) 空间 ^b。

• 一个使用 N Mb，其中 N 是输入的一部分的程序不使用 O(1) 空间（它使用 O(N) 空间）。

简而言之，当你看到 O(1) 时，心里就默念着 常量。

---

a. 例如，foo(n) = foo(n - 1)，在这里维护函数调用所需的堆栈空间是 O(n)。

b. 当关于 O 符号的材料评论忽略常数会带来麻烦时，这就是他们所说的。

- axiom

---

我非常喜欢关于1Tb常数的评论，我记得很久以前问过一位讲授符号学的讲师：“为什么我们不能将每个可能的输入（最多到程序的最大输入大小）计算到表格中，这样每个问题都可以是O(1)的？”当时我没有得到答案。或者在时间方面，为什么不休眠最坏情况所需的时间来确保恒定的时间。 - Vality

@Vality：讲师的答案是什么？我猜他的回答是，在理论上，没有输入大小的最大限制；在实际应用中，“恒定时间”并不值得以速度为代价。 - LarsH

@LarsH 我相信当时的讲师说这是系统的限制，但随后提到了图灵机，其中数字可以任意大。然而，他注意到了我的担忧，并表示我们不能盲目地应用符号而不考虑实践和限制。 - Vality

这段文字的意思是：大O符号用来表示随着输入规模增加，资源使用情况如何增长。不能仅凭“总是少于10年（或TB）”就说它是常数时间复杂度，因为这并不能告诉你随着输入规模增加会发生什么。有限性不是问题——即使问题本身规定输入大小受到某个常数的限制，你仍然想知道某些算法在输入规模增加时表现如何，直到达到那个常数为止。 - johncip

@prosfilaes：现在你只是在让自己尴尬。为了你自己的利益，请停止。我正在删除所有我的评论，建议你也这样做，并找一本关于递归函数理论的好书。（提示：递归函数数量是可数的，这是一个基本且微不足道的性质） - nomen

Answer 3

如果您的递归深度取决于输入大小（通常是这样），那么是的：您将使用无限量的堆栈内存。要求使用固定数量的内存来解决问题。

- Thilo

Answer 4

关于其他回答告诉你必须使用的栈的数量为 O(1) ，并且无论输入的大小如何都必须保持恒定，如果您希望以递归方式解决问题，那么它只留下两种可能性：

• 固定深度递归，这意味着限制函数递归的次数。
• 尾递归，这意味着调用函数的递归必须是评估的最后一件事，以触发TCO。 （尾递归优化）粗略地说，这意味着由于递归调用是在函数执行中发生的最后一件事情，因此不会将调用上下文推送到堆栈上，而是将现有的调用上下文覆盖为新的上下文，实际上只使用恒定的堆栈空间量。

- Laurent LA RIZZA

---

即使堆栈深度不是严格恒定的，算法在“所有实际目的”上也可能是O（1）。例如，一些数据结构需要O（lg（lg（N）））堆栈空间，并且可能需要一个集合的项超过宇宙中的所有电子才能达到十个堆栈深度。这样的事情从技术上讲不会是O（1），但可以将其视为是O（1）。 - supercat

Answer 5

如果您使用递归来解决这个问题，那么您使用堆栈将数据传递到递归树下方。在这方面，您通常使用的空间不止 O(1)。

我同意被接受的答案，但我想指出，如果您使用支持尾调用优化的语言（如Clojure），则可以使用O(1)空间解决问题，而使用不具有此功能的语言（如Java）会使用更多的空间。

因此，正确的答案也取决于所使用的语言。

- Adam Arold

---

虽然您可以使用recur手动消除尾调用，但由于JVM的限制，Clojure中没有尾调用优化。相关答案 - Andrew T

Answer 6

O(1)的存储复杂度意味着您的算法必须使用恒定数量的存储空间。也就是说，它在处理10个元素和1000个元素时使用的存储空间应该是相同的。

为了实现这一点，您可能应该使用迭代。

- David Carpenter