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

Question

如果给出了编程问题中的上述条件并且我使用递归来解决它,那么我是否违反了约束条件？这可能是因为递归也使用堆栈？这样对吗？

Answer 1

如果堆栈的深度(递归)是恒定的并且相对于输入的大小没有改变,那么递归解决方案可以是O(1)额外的空间.

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

但是,请记住,可能会强制使用O(1)约束来强制您选择特定的(可能是非递归的)算法,因此即使您知道正在使用的编译器,依赖尾部调用优化也可能是不明智的.对您的代码进行了相关的转换.至少,如果您依赖它,您应该明确说明并证明您期望通过参考语言规范,编译器文档和/或反汇编来实现TCO.

不过,这是一种不同寻常的递归.通常随着输入的增长它会变得更深. (17认同)
@Thilo一个例子是一个基于运算符优先级的解析器,其中`parse(9)`调用`parse(8)`,它为每个优先级的运算符调用`parse(7)`等. (9认同)
尾递归还可以导致没有堆栈空间用于支持尾调用消除的语言. (7认同)
@delnan,如果移动的总数有限,则游戏的搜索算法可能具有固定数量的呼叫. (4认同)
@delnan无论如何,这是我在生产代码中真正看到过的东西.至于Perreal的例子,如果游戏总是看起来完全(例如)前进四步,它仍然可以用固定深度递归来实现. (2认同)
@einpoklum,尾递归非常依赖于语言,所以它不能用于一般声明.我想我们可以说尾递归不是在运行时的递归. (2认同)

Answer 2

extra allowed space is O(1)

意味着你的程序只能使用一定量的空间C.

按照big-O的定义,这意味着程序所需的空间不能取决于输入的大小,尽管C可以任意大.

因此,如果递归取决于输入^a(通常是这种情况),则程序所需的空间不是O(1).

进一步澄清:

该程序总是利用1 Mb使用O(1)空间.

总是使用的程序1 Tb是使用O(1)空间^b.

它使用一种程序N Mb,其中,N为输入,不使用O(1)的空间,(它使用O(N)空间).

长话短说,无论何时你阅读O(1),只需要在心理上用常数替换它.

一个.例如,foo(n)= foo(n - 1),这里维护函数调用所需的堆栈空间是O(n)

湾 当O符号上的材料评论被忽略的常量如何麻烦时,这就是他们所说的

我非常喜欢关于1Tb常数的评论,我记得很久以前问过一位讲授课程的讲师"为什么我们不能只计算每一个可能的输入(达到程序的最大输入大小)到一个表格,然后每一个问题可能是O(1),当时我没有得到答案.或者在时间的情况下,为什么不只是睡觉,最坏的情况需要确保恒定的时间. (4认同)
这可能应该用于聊天,但是为了记录,Big-O用于显示资源使用量与输入大小相比的增长情况.你不能只说"它总是需要不到10年(或TB),因此它是恒定的",因为这并不能告诉你随着输入的增长会发生什么.有限度不是问题 - 即使问题本身决定了输入大小受某些常数的限制,你仍然想知道某些算法在输入大小的情况下如何增长*达到该常数.* (4认同)
@LarsH当时的讲师我认为这是系统的限制,但后来提到图灵机,其数字可能是任意大的.然而,他确实注意到我的担忧,并说我们不能盲目地应用符号而不考虑实践和限制. (2认同)

Answer 3

如果递归的深度根据输入的大小(通常是这样)而增长,那么是:您将使用无限量的堆栈内存.要求是用固定数量的内存来解决问题.

Answer 4

关于其他答案告诉你必须使用的堆栈数量O(1),并且必须保持不变,无论输入的大小如何,如果你想以递归的方式解决问题,它只会给你两种可能性:

固定深度递归,这意味着限制函数递归的时间.
尾递归,这意味着对函数的递归调用必须是最后要评估的东西,因此要触发TCO.(尾调用优化)粗略地说,这意味着由于递归调用是函数执行中发生的最后一件事,而不是在堆栈上推送调用上下文,现有的调用上下文将被新的覆盖,有效地使用常量堆栈空间量.