algorithm - 递归函数的空间复杂度分析

Question

在典型的面试中，当被问及“算法的空间复杂度是多少”以及该算法是否是递归的时，面试通常是指“在算法的整个生命周期内调用帧堆栈的最大次数”，还是他意思是“在函数中创建的任何给定变量中元素的最大数量”？

在非递归算法中，后者的定义通常是空间复杂度的定义。但是在递归中，我们必须分别定义两者吗？

标签： algorithmrecursionspace-complexity

Answer 1

如果没有更多信息，“空间复杂度是多少”将指程序使用的总空间。那是堆栈和堆空间。