¿Está bien que la profundidad de la pila sea proporcional a algún tamaño de entrada?

Question

Al programar en Java (o en cualquier otro lenguaje de procedimiento para el caso), a menudo elijo entre resolviendo algo recursivamente frente a resolviéndolo iterativamente. La opción recursiva es a menudo más elegante que una solución iterativa, por lo que generalmente utilizo la solución recursiva. Con una excepción:

Preocupación por los desbordamientos de la pila Tiendo a evitar soluciones recursivas si la profundidad máxima de la pila es linealmente proporcional al tamaño de la entrada (o algo peor). Sin embargo, me doy cuenta de que en muchos otros lenguajes (incluso los que apuntan a la JVM como Scala y Clojure) muchos algoritmos, como los algoritmos de lista básica, por ejemplo, se expresan recursivamente cuando la profundidad máxima de la pila es proporcional a la longitud de la lista. ⁽¹⁾ Entonces, ¿están justificadas mis preocupaciones sobre los desbordamientos de pila en linear-stack-depth-algorithms?

TL; DR: ¿Qué "complejidad de profundidad de pila" se considera razonable? complejidad logarítmica, recursiva de búsqueda binaria, por ejemplo, O (log N) es sin duda bien, pero ¿qué hay de O (N), O (N log N), O (N 2 )? ¿Dónde dibujarías normalmente la línea? ⁽²⁾

^{(1) Soy consciente de que estas lenguas a veces apoya cosas como @tailrec, pero esta pregunta se refiere a Java, C#, etc.
(2) Tenga en cuenta que no estoy preocupado por sobrecarga de la CPU etc. Solo la profundidad de la pila.}

Answer 1

No puede responder a esto sin preguntarse qué tamaño de entrada desea admitir.

La complejidad del espacio lineal en la pila es absolutamente buena si está procesando un mazo de naipes, y probablemente sea completamente imposible si está utilizando grandes archivos de texto. Necesitas calcular cuál será el tamaño máximo de entrada para tu aplicación, o mejor dicho, la entrada más grande para la que no te importa que falle.

Hacemos esto todo el tiempo. Por ejemplo, cada vez que declaras una matriz en Java, sabes que la matriz no puede contener más de 2 elementos . ¿Eso importa? ¿Significa que el programa está roto? Probablemente no; pero a veces lo hace, si la enorme contribución es algo que desea ser capaz de manejar.

Así que no creo que pueda ser demasiado prescriptivo sobre esto.¿Qué dirías si alguien preguntara (en términos generales) a qué hora la complejidad estaba bien? Podría decir algunos principios generales: por lo general, lo lineal está bien, generalmente lo exponencial es malo ... pero la respuesta real es que depende de lo que esté haciendo.

Answer 2

La complejidad de la profundidad de la pila es una cosa a considerar, pero otra cosa es el tamaño de la entrada en sí.

Si el problema excluye entrada grande de su dominio (por extendida período de tiempo en el proceso de desarrollo), entonces podemos ir a dar solución recursiva (por supuesto, la solución recursiva no debe exceder la capacidad de la pila con el la mayor entrada posible).

Si el tamaño de entrada no está definido, la profundidad de la pila O (1) o la profundidad de la pila O (log N) es aceptable, en mi humilde opinión. Es posible que O (log N) no sea aceptable si el límite superior práctico del tamaño de entrada es astronómicamente grande y excede la capacidad de la pila. Sin embargo, creo que ese caso sería bastante raro.