好的堆栈深度与某些输入大小成线性比例？

Question

当Java编程(或与此有关的任何其他程序语言),我经常选择递归地解决一些 VS 迭代解决它.递归选项通常比迭代解决方案更优雅,所以我通常会选择递归解决方案.除了一个例外:

担心堆栈溢出如果最大堆栈深度与输入的大小成线性比例(或更差),我倾向于避免递归解决方案.然而我意识到,在许多其他语言中(甚至是针对JVM的那些语言,例如Scala和Clojure),许多算法(例如基本列表算法)通常以递归方式表示,其中最大堆栈深度与列表的长度成比例.⁽¹⁾那么,我对线性堆栈深度算法中堆栈溢出的担忧是否合理？

TL; DR:什么"堆栈深度复杂度"被认为是合理的？对数复杂度,例如递归二进制搜索,O(log N)肯定没问题,但O(N),O(N log N),O(N ²)怎么样？你通常会在哪里划线？⁽²⁾

^{(1)我意识到这些语言有时支持像@tailrec这样的东西,但这个问题涉及Java,C#等.
(2)注意我并不关心CPU开销等.只是堆栈深度.}

Answer 1

如果不问自己想要支持什么大小的输入，就无法回答这个问题。

如果您正在处理一副扑克牌，则堆栈上的线性空间复杂度绝对没问题，但如果您正在处理巨大的文本文件，则可能完全没有希望。您需要计算出您的应用程序的最大输入大小是多少，或者更确切地说，您不介意它失败的最大输入大小。

我们一直这样做。例如，每次在 Java 中声明一个数组时，您都知道该数组中的元素不能超过 2 ³¹个。这有关系吗？这是否意味着程序已损坏？可能不会; 但有时确实如此，如果您希望能够处理大量输入。

所以我认为你不能对此太过规定。如果有人问（笼统地说）什么时间复杂度合适，你会怎么说？您可能会说一些一般原则：通常线性是好的，通常指数是不好的......但真正的答案是，这取决于你在做什么。